Задача Трекс-Пекс-Фекс (TREX)
Буратіно прийшов на Поле чудес, маючи P золотих монет та мішечок солі. Лисиця Аліса та кіт Базіліо повідомили йому, що якщо на цьому полі закопати T золотих монет (не обов’язково всі) і сказати заклинання «Трекс-пекс-фекс», то кількість монет подвоїться і можна буде викопати 2T золотих. Але якщо перед закопуванням T монет їх посолити, то після виголошення заклинання Буратіно викопає 2Т+1 монету. Буратіно має K порцій солі. Скільки разів потрібно сказати «Трекс-пекс-фекс», щоб отримати рівно S золотих?
Формат введення/виведення:
Програма TREX зчитує з клавіатури (стандартного пристрою введення) три цілих числа P, K, S (0≤K≤100, 0≤P,S≤109). Програма TREX виводить на екран число N – мінімальну кількість заклинань «Трекс-пекс-фекс», а потім N рядків, кожен з яких містить пару чисел – кількість закопаних монет та число «1» або «0». Одиниця виводиться, якщо золоті потрібно солити, і нуль – якщо ні. У випадку існування різних послідовностей дій Буратіно з мінімальною кількістю заклинань «Трекс-пекс-фекс» можна вивести будь-яку з них. Якщо отримати задану кількість монет неможливо, виводиться єдине число «−1».
Приклад:
| Введення | Виведення |
| 1 2 20 | 41 02 15 010 0 |