Єгипетські дроби
У часи Середнього царства Єгипту єгиптяни винайшли новий спосіб запису дробів. Додавання певного символу до ієрогліфа для цілого числа означало обернене цього числа. Це дозволяло легко записувати дроби виду 1 / n (названі одиничними дробами) — просто додайте символ оберненого числа до ієрогліфа для n.
Не існувало прямого способу представлення дробу виду m / n, де m > 1. Натомість такі дроби записувалися як сума одиничних дробів. Наприклад, дріб 3 / 4 могла бути записана як:
Зверніть увагу, що кілька сум можуть давати один і той самий результат; наприклад, також можна записати як
Ваше завдання — взяти дріб і записати її як суму одиничних дробів, використовуючи "жадібний" алгоритм. У жадібному алгоритмі ви послідовно віднімаєте найбільшу можливу одиничну дріб, поки не залишиться нуль. Наприклад, для дробу жадібний алгоритм знайде суму за три кроки наступним чином:
Зверніть увагу, що на кожному кроці ми віднімали найбільшу можливу одиничну дріб з залишку нашої початкової дроби.
Необхідно додати одне додаткове обмеження, щоб наші рішення не ставали занадто великими: кожного разу, коли ми віднімаємо одиничну дріб, ми повинні залишатися з дробом, знаменник якого строго менший 1,000,000. Наприклад, для дробу перші дві одиничні дроби, які ми віднімемо, будуть і , залишаючи нас з . У цей момент найбільша одинична дріб, яку ми могли б відняти, буде , залишаючи нас з
На жаль, це залишає нас з дробом, знаменник якого більше 1,000,000, тому ми не можемо використовувати цю одиничну дріб у нашій сумі. Ми переходимо до наступної найбільшої одиничної дроби, , яка залишає нас з
Оскільки остаточна відповідь зводиться до дробу зі знаменником менше 1,000,000, ми можемо використовувати цю одиничну дріб, залишаючи нас з остаточною відповіддю .
У цьому випадку нам довелося пропустити лише одну дріб. Однак у загальному випадку вам, можливо, доведеться пропустити багато дробів, щоб знайти підходящу. Поки ви шукаєте, вам доведеться виконувати обчислення з багатьма дробами з великими знаменниками; переконайтеся, що ви робите це ефективно, інакше ваша програма може зайняти занадто багато часу на виконання.
Також переконайтеся, що ви використовуєте тип даних, достатньо великий, щоб вмістити великі числа, з якими ви працюєте. Незважаючи на те, що ми обмежили знаменники до 1,000,000, вам, можливо, доведеться обчислювати проміжні значення зі знаменниками до 10^12. Для зберігання таких значень знадобиться 64-бітне ціле число (long у Java, long long у C/C++).
Нарешті, варто зазначити, що за своєю природою жадібний алгоритм завжди знайде якусь відповідь, що складається з дробів зі знаменниками менше 1,000,000, оскільки, принаймні, будь-яка дріб може бути представлена як сума одиничних дробів з її власним знаменником. Наприклад:
Вхідні дані
Вхідні дані будуть складатися з послідовності дробів; по одній на рядок. Кожен рядок міститиме лише два цілі числа M і N, де 1 < M < N < 100, що представляють дріб . M і N не матимуть спільних дільників, більших 1. Кінець вхідних даних буде позначено двома нулями: 0 0.
Вихідні дані
Для кожної вхідної дроби ви повинні вивести один рядок, що містить числа D[1] ≤ D[2] ≤ D[3] ≤ … такі, що:
Це повинна бути перша сума, отримана за допомогою жадібного пошуку при дотриманні обмеження на знаменник у 1,000,000. Кожне число повинно бути відокремлене одним пробілом, без початкових або кінцевих пробілів.