Оптимальна програма
Як ви знаєте, написання програми, справа досить часто далеко не така проста, як може здатись на перший погляд. І цей процес стає ще складнішим, якщо вашв програми повинні працювати якомога швидше. А іноді є вагомі підстави, щоб вони були швидкими. У багатьох об'ємних програмних кодах, такі як операційні системи та бази даних, є "вузькі місця" - сегменти коду, які будуть виконуватись знову і знову, і "жерти" значну частину від загального часу роботи. Як правило, цю частину коду приходиться переписувати на асемблері, тому що навіть невелика економія часу роботи буде дуже важлива, особливо якщо код виконується міліарди разів.
У цій задачі ми будемо розглядати задачу автоматизації генерації оптимального асемблерного коду. Для заданих функцій (у вигляді ряду вхідних/вихідних пар), ви повинні придумати найкоротшу програму, яка обчислює ці функції.
Ваша програма буде працювати на основі стекової машини, яка підтримує лише п'ять команд: ADD, SUB, MUL, DIV и DUP. Перші чотири команди беруть два верхніх елементи зі стеку і замінюють їх у стеці сумою, різницею, добутком чи діленням націло відповідно. Команда DUP добавляє у вершину стеку додадткову копію самого верхнього елементу у стеці.
Таким чином, якщо команди застосовуються до стеку з двома верхніми елементами a та b, то в результаті стек виглядатиме наступним чином:
На початку виконання програми стек буде містити лише одне вхідне ціле число. У кінці обчислень стек повинен містити лише одне цвле число, це число є результатом обчислень.
Є три випадки, коли стекова машина входить у стан помилки:
Команда DIV не виконується, якщо самий верхній елемент стеку дорівнює 0.
Команди ADD, SUB, MUL і DIV не будут виконані, якщо стек містить лише один елемент.
У результаті виконання операція отримуємо значення більше, ніж 30000 за абсолютною величиною.
Вхідні дані
Вхід складається з серії опису функцій. Кожен опис починається з рядка, який містить ціле число n (n ≤ 10), кількість пар входів/виходів. Наступні два рядки містять n цілих чисел - кожне з них відповідно вхідні та вихідні значення пар чисел. Вхідні числа будуть не більші 30000 за абсолютною величиною.
Вхідні дані завершуються рядком зі значенням n = 0. Цей тест не опрацьовуєеться.
Вихідні дані
Ви повинні написати найкоротшу програму, яка обчислює функцію f, таку, що f(x_i) = y_i для усіх i {1, ..., n}. Це означає, що програма не может вступати у стан помилки для заданих на вході x, хоча вона може війти в стан помилки для іншихх значень. Розглядати будемо лише ті програми, які мають не більше 10 заданих пар значень.
Для кожної функції опису спочатку виведіть номер опису. Патім виведіть послідовність команд, які складають найкоротшу програму для обчислення заданої функції. Якщо є більше ніж одна така програма, вивести лексикографічно найменшу. Якщо немає програми із не більше 10 команд, які обчислюють функцію, вивести рядок "Impossible". Якщо найкоротша програма складається з нуля команд, вивести "Empty sequence".
Виводьте порожній рядок між різними тестовими випадками.