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:

  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 …
  4. 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
2
3
4
3
30 10 20
41 15 30
18 13 18

output

1
2
3
2
7
1

Note

In the first testcase the temperature after 22 poured cups: 11 hot and 11 cold is exactly 2020. So that is the closest we can achieve.
In the second testcase the temperature after 77 poured cups: 44 hot and 33 cold is about 29.85729.857. Pouring more water won’t get us closer to t than that.
In the third testcase the temperature after 11 poured cup: 11 hot is 1818. That’s exactly equal to tt.

Translation

有两种水，一种是温度为 hh 的热水，另一种是温度为 cc 的冷水。会按照以下步骤进行操作：往一个足够大的桶里倒一杯热水；往这个桶里倒一杯凉水；倒一杯热水；以此类推……
桶中水的温度是已经倒入桶中水的平均温度，至少要倒一杯水，第一杯倒的水一定要是热水。
你要使经过若干次操作后，桶里的温度和 tt 尽可能接近。

Idea

可以发现，倒了 xx 轮水后，桶中有 xx 杯热水，xx 杯冷水，桶中的水温为 xh+xc2x=h+c2\frac{xh+xc}{2x}=\frac{h+c}{2}，此时再倒一杯热水就会改变桶中的水温，再倒一杯冷水水温会再次达到 h+c2\frac{h+c}{2}；因此，若 h+c2=t\frac{h+c}{2}=t，只需要倒 22 杯水即可。
若 h+c2≠t\frac{h+c}{2}\neq t，那么设倒 xx 轮水后，再倒一杯热水来调节温度，此时桶中水温为 (x+1)h+xc2x+1\frac{(x+1)h+xc}{2x+1}；令 (x+1)h+xc2x+1=t\frac{(x+1)h+xc}{2x+1}=t，解得 x=h−t2t−h−cx=\frac{h-t}{2t-h-c}。我们排除 h+c2=t\frac{h+c}{2}=t 的情况。若 h=th=t，则有 x=0x=0，联系实际，显然倒一杯热水就行，答案是 11。若 h>th>t，当 t>h+c2t>\frac{h+c}{2} 时，x>0x>0，由于 xx 是整数，我们需要讨论 xx 取 x1=⌊h−t2t−h−c⌋x_1=\left\lfloor\frac{h-t}{2t-h-c}\right\rfloor 和 x2=⌈h−t2t−h−c⌉x_2=\left\lceil\frac{h-t}{2t-h-c}\right\rceil 两个临界值时的情况；当 t<h+c2t<\frac{h+c}{2}，x<0x<0，因为加热水会拉高桶内的温度，结合实际情况，当桶内温度到达 h+c2\frac{h+c}{2} 时，不应该再加热水，因此只需要倒一轮水即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: CF1359C
Date: 01/14/2020
Description: Math
*******************************************************************/
#include<iostream>
#include<cmath>
using namespace std;
typedef long long ll;
typedef double db;
int _;
db h,c,t;
db f(ll);//计算温差
int main(){
	for(cin>>_;_;_--){
		cin>>h>>c>>t;
		ll ans;
		if(t==h){
			ans=1;
		}else if(t<=(h+c)/2.0){
			ans=2;
		}else{
			ll x=(h-t)/(2*t-h-c);
			//x或x+1轮水 再倒一杯热水
			ans=f(2*x+1)<=f(2*x+3)?2*x+1:2*x+3;
		}
		cout<<ans<<endl;
	}
	return 0;
}
db f(ll day){
	ll x=day+1>>1;//热水
	ll y=day>>1;//冷水
	db tb=(x*h+y*c)/(db)day;//水温
	return fabs(tb-t);//温差
}