Problem: http://www.lightoj.com/volume_showproblem.php?problem=1393

The problem is categorized as Nim in LightOJ. I solved the remaining 4 problems in the same category with no major difficulties (here), however I am stuck on this one.

Could someone please hint to the solution ? Is it only "basic" Nim, or is there something else I need to learn ?

Thanks.

Could you please tell me some problems which could be solved using matrix exponentiation on codeforces or other judges ?

Thanks.

http://codeforces.com/problemset/problem/7/D

Can someone please explain to me the problem ? I don't understand how the result was 6 for the second input case.

http://www.codeforces.com/gym/100155/problem/B

Does anyone have a clue how approach/solve the problem ?

This was the first time I implement ternary search, I figured out what it is, and how it matches to 215D - Hot Days, however, I keep getting Wrong answer on test 15 which seems to be common for a some of the other contestants as well (http://www.codeforces.com/contest/215/status)

Could someone help me please to figure out the bug in my solution ?

#define ll long long
ll n,m;
ll z,ti,Ti,xi,costi;
ll f(ll y) { // cost if got y buses
	ll slc=m-((y-1ll)*z);
	ll e=slc>z?(slc*xi):0ll;
	return (y*costi)+e;
}
ll r(ll a,ll b) { // ternary search
	assert(b>=a);
	if((b-a)==0) return f(a);
	if((b-a)==1) return min(f(a),f(b));
	ll x=a+(b-a)/3;
	ll y=b-(b-a)/3;
         assert(x<y);
	if(f(x)>=f(y)) return r(x+1,b);
	return r(a,y-1);
}
int main() {
//    freopen("me.txt","r",stdin);
	cin>>n>>m;
	ll res=0;
	for(int i=0;i<n;++i) {
		cin>>ti>>Ti>>xi>>costi;
		if(Ti>ti) {
			z=Ti-ti; //maximum capacity per bus, except last bus
			ll g=round(ceil((double)m/z)); // maximum number of buses
			res+=r(1ll,g);
		} else {
			res+=(costi+(m*xi));
		}
	}
	cout<<res<<endl;
    return 0;
}

Thanks a lot :)

Edit: I managed to get AC when I brute forced the entire interval when b-a < 1000 (got WA on case 29 when tried b-a < 100):

if(b-a < 1000) {
	ll res=f(a);
	for(int i=a+1;i<=b;++i) res=min(res,f(i));
	return res;
}

I thought 215B - Olympic Medal was an easy problem, I got the relation fairly easily, but then it gave me WA at test 10.

My first submission was:

double r2=sqrt( ((double)((r1*r1)*(b)*(p1)))/(a*p2+b*p1));

Where r1 and p1 are the maximum possible and p2 is the minimum possible, based on that relation, where its directly proportional with r1 and p2 and inversly proportiona with p2.

So I thought I may need long double, re-submitted with long double, WA again.

Then I thought the std sqrt function was not accurate enough, coded my own sqrt function.

Long story short, I made 11 WAs all trying to figure out whats wrong, until in the end I used the inverse of the relation, and voila AC from the first time !

long double r2=(1.0/(r1*r1))*(((a*p2)/(b*p1))+1); r2=pow(r2,-0.5);

But it was totally useless..the 11 WAs made my rank be 877, the lowest I ever got (so far :/)

I just hate those double precision problems...

Edit: Thanks to riadwaw, I knew what was the mistake. 5000^4 > INT_MAX, I should have kept the numerator as double to avoid the overflow. I totally admit it was my mistake for overlooking the constraints. Hopefully it would be another trick which no one would fall into again :)