CF1359C Mixing Water
CF13959C - From Educational Codeforces Round 88 (Rated for Div. 2)
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:
- take one cup of the hot water and pour it into an infinitely deep barrel;
- take one cup of the cold water and pour it into an infinitely deep barrel;
- take one cup of the hot water …
- and so on …
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 tb, then the absolute difference of tb and t (|tb−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
The first line contains a single integer T (1≤T≤3⋅104) — the number of testcases.
Each of the next T lines contains three integers h, c and t (1≤c<h≤106; c≤t≤h) — the temperature of the hot water, the temperature of the cold water and the desired temperature in the barrel.
Output
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.
Example
input
1 | 3 |
output
1 | 2 |
Note
In the first testcase the temperature after poured cups: hot and cold is exactly . So that is the closest we can achieve.
In the second testcase the temperature after poured cups: hot and cold is about . Pouring more water won’t get us closer to t than that.
In the third testcase the temperature after poured cup: hot is . That’s exactly equal to .
Translation
有两种水,一种是温度为 的热水,另一种是温度为 的冷水。会按照以下步骤进行操作:往一个足够大的桶里倒一杯热水;往这个桶里倒一杯凉水;倒一杯热水;以此类推……
桶中水的温度是已经倒入桶中水的平均温度,至少要倒一杯水,第一杯倒的水一定要是热水。
你要使经过若干次操作后,桶里的温度和 尽可能接近。
Idea
可以发现,倒了 轮水后,桶中有 杯热水, 杯冷水,桶中的水温为 ,此时再倒一杯热水就会改变桶中的水温,再倒一杯冷水水温会再次达到 ;因此,若 ,只需要倒 杯水即可。
若 ,那么设倒 轮水后,再倒一杯热水来调节温度,此时桶中水温为 ;令 ,解得 。我们排除 的情况。若 ,则有 ,联系实际,显然倒一杯热水就行,答案是 。若 ,当 时,,由于 是整数,我们需要讨论 取 和 两个临界值时的情况;当 ,,因为加热水会拉高桶内的温度,结合实际情况,当桶内温度到达 时,不应该再加热水,因此只需要倒一轮水即可。
Code
1 | /****************************************************************** |