?
# | Author | Problem | Lang | Verdict | Time | Memory | Sent | Judged | |
---|---|---|---|---|---|---|---|---|---|
81828965 |
Practice: _nicktz1408_ |
1359C - 9 | C++14 (GCC 6-32) | Wrong answer on test 3 | 109 ms | 8 KB | 2020-05-28 23:44:13 | 2020-05-28 23:44:13 |
#include <iostream> #include <string> #include <vector> #include <algorithm> #include <utility> #include <queue> #include <stack> #include <set> #include <map> #include <cmath> #include <functional> #include <random> using namespace std; bool isBigger(int target, long long d, long long l) { long long m = 2 * l + 1, div = l + 1; long long left = target * m; long long right = d * div; return left > right; } //Get temperature given l (m = 2 * l + 1) and diff long double getC(long long l, long long d) { long long m = 2 * l + 1, div = l + 1; double ans = (long double)d / (long double)m * div; return ans; } void solve() { int h, c, t; cin >> h >> c >> t; if (t >= h) cout << 1 << endl; else if (2 * t <= h + c) cout << 2 << endl; else { int d = h - c, redTarget = t - c; //For odd number of moves we have: //temperature (target) = ((n + 1) * h + n * c) / (2n + 1) = ((n + 1) * (c + diff) + n * c) / (2n + 1) = // = ((2n + 1) * c + (n + 1) * diff) / (2n + 1) = c + (n * c) / (2n + 1) //So, we substract c from both sides and we get: //reducedTarget = (n * diff) / (2n + 1) = (ceil(m / 2) * diff) / m //Now, we can try to find the best value of m by binary searching //get redTarget as close as to d * (ceil(m / 2) / m), where m is odd long long l = 1, h = 1000000000; while (l < h) //get first that is smaller { long long mid = (l + h) / 2; if (isBigger(redTarget, d, mid)) h = mid; else l = mid + 1; } int firstSmaller = l, lastBigger = l - 1; if ((long double)redTarget - getC(firstSmaller, d) > getC(lastBigger, d) - (long double)redTarget) cout << 2 * lastBigger + 1 << endl; else cout << 2 * firstSmaller + 1 << endl; } } int main() { cin.tie(0); ios::sync_with_stdio(0); int T; cin >> T; for (int t = 1; t <= T; t++) solve(); return 0; }
?
?
?
?