← 返回题目列表

AtCoder · icpc2015summer_day3_e

E. 确切的掉落次数

中文机器翻译题面 查看原题

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

Exact Number of Drops - 原题 PDF
赛事原始英文题册页面
可复制的 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