AtCoder镜像页只保留了来源名称;以下原题页取自作品原始英文题册,现已完整保存到本地。

可复制的 PDF 提取文本
Gennady Korotkevich Contest 1
Petrozavodsk Training Camp, Day 1, Friday, August 23, 2013
Problem E. Exact Number of Drops
Input le: end.in
Output le: end.out
Time limit: 2 seconds
Memory limit: 256 megabytes
Hmm... I asked for 400 drops, but there are 402
here.
400 drops, we never make mistakes.
Russian cartoon The Mystery of the Third Planet
Do you think that managing a restaurant is easy? That is not the case when all clients are pretty
demanding.
You are managing a restaurant, and every day a lot of people come and ask you to give them
some drinks. As your restaurant has just recently opened, you don't have any vessels except two,
which can accommodate a drops of liquid and b drops of liquid, respectively.
In order not to make your clients wait (or at least to minimize their waiting time), you always
have to determine the minimal number of steps required to obtain exactly c drops of liquid in one
of the vessels.
At the beginning both vessels are empty. The following operations are counted as steps:
• emptying a vessel;
• lling a vessel;
• pouring liquid from one vessel to the other (without spilling) until one of the vessels is either
full or empty.
Eventually you became tired to do it all by hand and decided to write a program which will help
you calculate the minimum number of steps required in all these cases.
Input
The rst line of the input le contains the number of test cases T (1 ≤T ≤105). The next T lines
contain one testcase each and consist of three integers a, b and c (1 ≤a, b, c ≤109).
Output
For each test case, output the minimum number of steps required to obtain exactly c drops of
liquid in one of the vessels or −1 if this is impossible.
Examples
end.in end.out
2 4
2 5 4 -1
5 3 7
Page 5 of 10