General
 
 
# 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
→ Source
#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;
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details