2823. Automatic Cash Terminal

单点时限: 2.0 sec

内存限制: 256 MB

The automatic teller machine (ATM) has a lot of banknotes of two different values. When a person who uses the terminal requests some amount, the machine issues exactly this amount of money (of course, if this amount does not exceed a balance of the user‘s account). Most people do not like to carry a huge bundle of banknotes, therefore the machine must issue requested amount using minimal possible number of banknotes. Your task is to write a program that determines the number of banknotes of each value that should be issued by the machine so that the user receives the requested amount and the total number of banknotes is minimal. You may assume that the number of banknotes of each value is not limited.


The first number in the input gives the number of test cases. A single line for each case contains three integers a, b (the values of banknotes in the machine) and S (the amount of money requested by the user). (1≤a,b≤10000, a≠b, 0≤S≤109). Integers in each line are separated by a space.


For each test case print a single line in the output with two integers – numbers of banknotes of each value which must be issued by ATM. In case when it‘s not possible to issue requested amount, print the word “Impossible” (without quotes).


1 10 23
3 2 7
4 6 2
3 2
1 2

26 人解决,40 人已尝试。

30 份提交通过,共有 130 份提交。

5.2 EMB 奖励。

创建: 11 年,2 月前.

修改: 4 年,3 月前.

最后提交: 1 年前.

来源: Ukrainian