Время

15:41:11
24 May 2012
Версия для печати

Банкомат

prb696   В банкомате находится достаточно большое количество купюр двух различных достоинств. Человек, пользующийся банкоматом, может вводить некоторую сумму, и банкомат должен выдать ему в точности эту сумму (если конечно она имеется у данного человека на счету). Естественно, никому не хочется таскать с собою целый пресс денег, поэтому банкомат должен выдавать сумму минимально возможным числом банкнот.

   Напишите программу, определяющую сколько банкнот каждого достоинства должен выдать банкомат, чтобы получилась заданная сумма, а общее количество банкнот было минимальным.


Технические условия

   Входные данные

   В первой строке входного файла задается количество тестов. В каждой из последующих строк записаны три целых числа: a, b (достоинства купюр, находящихся в банкомате) и S (требуемая сумма). (1a, b 10000, a b, 0 S 109).

   Выходные данные

   В выходной файл необходимо вывести два числа – количество купюр каждого типа, которые должны быть выданы банкоматом. В случае невозможности выдачи заданной суммы, выведите слово "Impossible" (без кавычек).


Информация о задаче

Лимит времени: 1 секунда
Лимит памяти: 64 MB
Баллы за пройденный тест: 1.5873
Сложность: 29% 46/65

Пример

Пример входных данных

3
1 10 23
3 2 7
4 6 2

Пример выходных данных

3 2
1 2
Impossible


← Range Variation Query Список задач Коробка →