SPOJ.com - Problem HOMEC

HOMEC - Homecoming

It was a tough battle but the humans won it comprehensively in the end. It was made possible due to combined efforts of both the human tribes but the 2^nd tribe wants to take all the credit and rule the world by killing the first tribe. Now that the war has ended, the tribes would be returning to their cities. The warriors would be travelling over the bridges built earlier, in small groups. It is then that the 2^nd tribe wants to execute their plan. The king of the 1^st tribe knows this and wants to ensure that this doesn’t happen. So he puts a constraint, that it should never happen at any time that the number of people of the 2nd tribe outnumber the number of people of the 1st tribe either on both sides or on the bridge. Also, it is night time and a torch needs to be carried for travel to be possible. But unfortunately, there’s just one torch available and hence at least someone would have to come back every time, with the torch. To make matters worse, there’s a restriction on the number of warriors that can cross the bridge in one pass.

Input

The first line of input contains test cases t (1<=t<=50). Then t lines follow, one for each test case. It contains three integers, n (1<=n<=100) the number of warriors of first tribe, m (1<=m<=100) the number of warriors of second tribe and c (1<=c<=50) the number of warriors that can cross the bridge in a single pass.

Output

Display a single line for each test case, containing a single integer which gives the total number of times the bridge is crossed. A round trip counts as 2. Output -1 if travel is not possible with the given constraints.

Example

Input:
3
3 3 2
4 4 2
100 100 20

Output:
11
-1
21

Submit solution!

Added by:	Troika::Bytes
Date:	2010-02-18
Time limit:	1s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: PERL6

hide comments



2024-11-01 16:37:48 anonymous > It contains three integers, n (1<=n<=100) the number of warriors of first tribe, m (1<=m<=100) the number of warriors of second tribe There are inputs with n = 0 or m = 0. > So he puts a constraint, that it should never happen at any time that the number of people of the 2nd tribe outnumber the number of people of the 1st tribe either on both sides or on the bridge. This part of the problem statement requires a creative interpretation. At no time, and in no place (either side of a river or on a bridge) where the people from the 1st tribe are present, can the 2nd tribe outnumber them.
2019-10-19 21:45:49 :D In steps 5 and 7 you are leaving more of #2 tribe on the right side (1,3 and 2,3). Last edit: 2019-10-19 21:46:09
2019-01-03 00:12:37 I have no idea how we get the sample output. If the condition is 'it cannot happen that [# of second tribe > # of first tribe on both left and right side] or [# of second tribe > # of first tribe crossing on bridge]' then I can solve first case in 9 crossings: 0. 3,3 0,0 (1,1 walk) 1. 2,2 1,1 (1,0 walks back) 2. 3,2 0,1 (1,1 walk) 3. 2,1 1,2 (1,0 walks back) 4. 3,1 0,2 (1,1 walk) 5. 2,0 1,3 (1,0 walks back) 6. 3,0 0,3 (2,0 walk) 7. 1,0 2,3 (1,0 walks back) 8. 2,0 1,3 (2,0 walk) 9. 0,0 3,3 every walk had # first >= #second on the bridge, and at no point did the second tribe have more people on both sides (the left side always had #first >= #second, even during walks). In case the condition is 'it can never happen that #second > #first on either side, or #second > #first on bridge', then the first case is impossible as at some point a single warrior has to cross the bridge alone - if he is from second tribe, then #second>#first on bridge, and if he is from first tribe, then the #second tribe left on sides is greater, so on one side it will have #second>#first. Anyone know what the problem is actually asking? Last edit: 2019-01-03 00:13:01