Банкомат
В банкомате находится достаточно большое количество купюр двух различных достоинств. Человек, пользующийся банкоматом, может вводить некоторую сумму, и банкомат должен выдать ему в точности эту сумму (если конечно она имеется у данного человека на счету). Естественно, никому не хочется таскать с собою целый пресс денег, поэтому банкомат должен выдавать сумму минимально возможным числом банкнот.
Напишите программу, определяющую сколько банкнот каждого достоинства должен выдать банкомат, чтобы получилась заданная сумма, а общее количество банкнот было минимальным.
Технические условия
Входные данные
В первой строке входного файла задается количество тестов. В каждой из последующих строк записаны три целых числа: a, b (достоинства купюр, находящихся в банкомате) и S (требуемая сумма). (1 ≤ a, 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 | Список задач | Коробка → |
