Баланс
Ms. Ійо Кіффа-Австраліс має ваги та лише два види гир для вимірювання дози ліків. Наприклад, щоб виміряти 200 мг аспірину, використовуючи гирі по 300 мг та 700 мг, вона може покласти одну гирю 700 мг на бік з ліками та три гирі по 300 мг на протилежний бік (Рисунок 1). Хоча вона могла б покласти чотири гирі по 300 мг на бік з ліками та дві гирі по 700 мг на інший (Рисунок 2), вона не вибере це рішення, оскільки менш зручно використовувати більше гир.
Вам потрібно допомогти їй, розрахувавши, скільки гир потрібно.
Рисунок 1. Вимірювання 200 мг аспірину, використовуючи три гирі по 300 мг та одну гирю 700 мг
Рисунок 2. Вимірювання 200 мг аспірину, використовуючи три гирі по 300 мг та дві гирі по 700 мг
Вхідні дані
Вхідні дані складаються з послідовності наборів даних. Набір даних - це рядок, що містить три додатні цілі числа a, b та d, розділені пробілом. Виконуються наступні співвідношення: a ≠ b, a ≤ 10000, b ≤ 10000, та d ≤ 50000. Ви можете припустити, що можливо виміряти d мг, використовуючи комбінацію гир по a мг та b мг. Іншими словами, вам не потрібно розглядати випадки "немає рішення".
Кінець вхідних даних позначається рядком, що містить три нулі, розділені пробілом. Це не набір даних.
Вихідні дані
Вихідні дані повинні складатися з рядків, кожен з яких відповідає вхідному набору даних (a, b, d). Вихідний рядок повинен містити два невід'ємні цілі числа x та y, розділені пробілом. Вони повинні задовольняти наступні три умови.
Ви можете виміряти d мг, використовуючи x гир по a мг та y гир по b мг.
Загальна кількість гир (x + y) є найменшою серед тих пар невід'ємних чисел, що задовольняють попередню умову.
Загальна маса гир (ax + by) є найменшою серед тих пар невід'ємних чисел, що задовольняють попередні дві умови.
Жодних зайвих символів (наприклад, зайвих пробілів) не повинно бути у вихідних даних.