Output: Standard Output
Time Limit: 2 Seconds
We have many planes at a place A, each of them can fly a/b of the world with a
full tank. For example, if a = 1, b = 2, Each plane can cover half of the
world(that is, from A to B), shown in picture 1:
With the help of
hi-technology, planes can exchange fuel in no time (but remember that the
amount of fuel a plane can carry cannot exceed the capacity of the tank at any
time!), we can use more planes to ensure that one of them flies across the
whole world, and all of them are able to be back to A at last.
For example, 5 planes are enough for a = 1, b =
2, shown in picture 2:
The picture below gives the explanation.
If you can figure it out yourself, just ignore the figure below (or next page)
So complicated, right? For simplicity, we
restrict the way to the following:
The first line of the
input contains a single integer t(1 <= t <= 50), the number of
test cases followed.
For each case, two
integers a and b(0 <= a,b <= 150) are separated by a single
space. Of course b will not be zero.
For each test case,
print the case number and the minimal number of planes required. If 10000
planes are not enough, output a -1.
3 1 2 1 3 2 5 |
Case
1: 5 Case
2: -1 Case 3: 13
|
Problemsetter: Rujia Liu, Member of Elite
Problemsetters' Panel
Special Thanks: Shahriar
Manzoor (Drawing pictures)
Jimmy Mårdell (Alternate Solution)