|
|
back to boardDiscussion of Problem 1607. TaxiO(1) c++ solution and BEST EXPLANATION Posted by Mohamed 10 Sep 2022 21:02 i kinda changed the variables a = the first sum suggested by petr b = the ---------------------- taxi driver c = amount added by petr everytime d = ---------------- taxi driver we can say that at step n of bargaining: petr -> a + n*c taxi -> b - n*d where looking for a time when petr's suggestion is less than the drivers which means a + nc <= c - n*d but there sometime when petr suggest more than what the driver suggest the previous time. that's why i am comparing between the last petr's suggestion and the previous one of the driver a+c*n > b-d*(n-1). in this case petr says ok to the taxi driver and do not suggest more than that. void solve() { int a, c, b, d; cin >> a >> c >> b >> d; if (a >= b) { cout << a; return; } int n = (b-a)/(c+d); if ((b-1)%(c+d)!=0) n++; if (a+c*n > b-d*(n-1)) { cout << b - d*(n-1) << ln; } else { cout << a + n*c << ln; } } Edited by author 10.09.2022 21:11 Re: O(1) c++ solution and BEST EXPLANATION could you help explain why: if ((b-1)%(c+d)!=0) n++; Re: O(1) c++ solution and BEST EXPLANATION Posted by Timur R 25 Jun 2024 16:29 this is more simply code: int a, b, c, d; cin >> a >> b >> c >> d; if (a >= c) { cout << a; return; } int l = (c - a) / (b + d); a += b * l; c -= d * l; if (a + b <= c) cout << a + b; else cout << c; |
|
|