alphadr's blog

By alphadr, 12 years ago, In English

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;
}
  • Vote: I like it
  • 0
  • Vote: I do not like it