Mixing Water
Contest: Educational Codeforces Round 88 (Rated for Div. 2)
Difficulty rating: 1700
Tags: binary search, math

There are two infinite sources of water:

- hot water of temperature $$$h$$$;
- cold water of temperature $$$c$$$ ($$$c < h$$$).

You perform the following procedure of alternating moves:

1. take one cup of the hot water and pour it into an infinitely deep barrel;
2. take one cup of the cold water and pour it into an infinitely deep barrel;
3. take one cup of the hot water $$$\dots$$$
4. and so on $$$\dots$$$

Note that you always start with the cup of hot water.

The barrel is initially empty. You have to pour at least one cup into the barrel. The water temperature in the barrel is an average of the temperatures of the poured cups.

You want to achieve a temperature as close as possible to $$$t$$$. So if the temperature in the barrel is $$$t_b$$$, then the absolute difference of $$$t_b$$$ and $$$t$$$ ($$$|t_b - t|$$$) should be as small as possible.

How many cups should you pour into the barrel, so that the temperature in it is as close as possible to $$$t$$$? If there are multiple answers with the minimum absolute difference, then print the smallest of them.

Input format:
The first line contains a single integer $$$T$$$ ($$$1 \le T \le 3 \cdot 10^4$$$) — the number of testcases.

Each of the next $$$T$$$ lines contains three integers $$$h$$$, $$$c$$$ and $$$t$$$ ($$$1 \le c < h \le 10^6$$$; $$$c \le t \le h$$$) — the temperature of the hot water, the temperature of the cold water and the desired temperature in the barrel.

Output format:
For each testcase print a single positive integer — the minimum number of cups required to be poured into the barrel to achieve the closest temperature to $$$t$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first testcase the temperature after $$$2$$$ poured cups: $$$1$$$ hot and $$$1$$$ cold is exactly $$$20$$$. So that is the closest we can achieve.

In the second testcase the temperature after $$$7$$$ poured cups: $$$4$$$ hot and $$$3$$$ cold is about $$$29.857$$$. Pouring more water won't get us closer to $$$t$$$ than that.

In the third testcase the temperature after $$$1$$$ poured cup: $$$1$$$ hot is $$$18$$$. That's exactly equal to $$$t$$$.

Example input:
3
30 10 20
41 15 30
18 13 18

Example output:
2
7
1

Editorial:
So there are two kinds of stops to consider: $$$k$$$ hot and $$$k$$$ cold cup and $$$(k + 1)$$$ hot and $$$k$$$ cold cups.
The first case is trivial: the temperature is always $$$\frac{h + c}{2}$$$. In the second case the temperature is always strictly greater than $$$\frac{h + c}{2}$$$. Thus, if $$$t \le \frac{h + c}{2}$$$, then the answer is $$$2$$$.
Let's show that otherwise the answer is always achieved through the second case.
The temperature after $$$(k + 1)$$$ hot cups and $$$k$$$ cold cups is $$$t_k = \frac{(k + 1) \cdot h + k \cdot c}{2k + 1}$$$. The claim is that $$$t_0 > t_1 > \dots$$$. Let's prove that by induction.
$$$t_0 = h, t_1 = \frac{2 \cdot h + c}{3}$$$. $$$c < h$$$, thus $$$t_0 > t_1$$$.
Now compare $$$t_k$$$ and $$$t_{k+1}$$$.
$$$$$$t_k > t_{k+1}$$$$$$
$$$$$$\frac{(k + 1) \cdot h + k \cdot c}{2k + 1} > \frac{(k + 2) \cdot h + (k + 1) \cdot c}{2k + 3}$$$$$$
$$$$$$\frac{k \cdot (h + c) + h}{2k + 1} > \frac{(k + 1) \cdot (h + c) + h}{2k + 3}$$$$$$
$$$$$$2k \cdot (k \cdot (h + c) + h) + 3k \cdot (h + c) + 3h > 2k \cdot ((k + 1) \cdot (h + c) + h) + (k + 1) \cdot (h + c) + h$$$$$$
$$$$$$2k \cdot (k \cdot (h + c) + h - (k + 1) \cdot (h + c) - h) > (k + 1) \cdot (h + c) + h - 3k \cdot (h + c) - 3h$$$$$$
$$$$$$2k \cdot (-(h + c)) > (-2k + 1) \cdot (h + c) - 2h$$$$$$
$$$$$$2h > (h + c)$$$$$$
$$$$$$h > c$$$$$$
We can also show that this series converges to $$$\frac{h + c}{2}$$$:
I'm sorry that I'm not proficient with any calculus but my intuition says that it's enough to show that $$$\forall k~t_k > \frac{h + c}{2}$$$ and $$$\forall \varepsilon \exists k~t_k < \frac{h + c}{2}$$$ with $$$k \ge 0$$$.
So the first part is:
$$$$$$\frac{(k + 1) \cdot h + k \cdot c}{2k + 1} > \frac{h + c}{2}$$$$$$
$$$$$$\frac{k \cdot (h + c) + h}{2k + 1} > \frac{h + c}{2}$$$$$$
$$$$$$2k \cdot (h + c) + 2h > (2k + 1) \cdot (h + c)$$$$$$
$$$$$$2h > h + c$$$$$$
$$$$$$h > c$$$$$$
And the second part is:
$$$$$$\frac{(k + 1) \cdot h + k \cdot c}{2k + 1} < \frac{h + c}{2} + \varepsilon$$$$$$
$$$$$$\frac{k \cdot (h + c) + h}{2k + 1} < \frac{h + c}{2} + \varepsilon$$$$$$
$$$$$$2k \cdot (h + c) + 2h < (2k + 1) \cdot (h + c) + (2k + 1) \cdot \varepsilon$$$$$$
$$$$$$2h < (h + c) + (2k + 1) \cdot \varepsilon$$$$$$
$$$$$$h < c + (2k + 1) \cdot \varepsilon$$$$$$
$$$$$$\frac{h - c}{\varepsilon} < 2k + 1$$$$$$
So that claim makes us see that for any $$$t$$$ greater than $$$\frac{h + c}{2}$$$ the answer is always achieved from the second case.
That allows us to find such $$$k$$$, that the value of $$$t_k$$$ is exactly $$$t$$$. However, such $$$k$$$ might not be integer. $$$\frac{(k + 1) \cdot h + c}{2k + 1} = t \leftrightarrow$$$ $$$\frac{k \cdot (h + c) + h}{2k + 1} = t \leftrightarrow$$$ $$$k \cdot (h + c) + h = 2kt + t \leftrightarrow$$$ $$$k \cdot (h + c - 2t) = t - h \leftrightarrow$$$ $$$k = \frac{t - h}{h + c - 2t}$$$.
The only thing left is to compare which side is better to round $$$k$$$ to. It seems some implementations with float numbers might fail due to precision errors. However, it's possible to do these calculations completely in integers.
Let's actually rewrite that so that the denominator is always positive $$$k = \frac{h - t}{2t - h - c}$$$. Now we can round this value down and compare $$$k$$$ and $$$k + 1$$$.
So the optimal value is $$$k$$$ if $$$|\frac{k \cdot (h + c) + h}{2k + 1} - t| \le |\frac{(k + 1) \cdot (h + c) + h}{2k + 3}| - t$$$. So $$$|(k \cdot (h + c) + h) - t \cdot (2k + 1)| \cdot (2k + 3) \le |((k + 1) \cdot (h + c) + h) - t \cdot (2k + 3)| \cdot (2k + 1)$$$. Otherwise, the answer is $$$k + 1$$$.
You can also find the optimal $$$k$$$ with binary search but the formulas are exactly the same and you have to rely on monotonosity as well. Also, these formulas can get you the better understanding for the upper bound of the answer.
Overall complexity: $$$O(1)$$$ or $$$O(\log h)$$$ per testcase.