Оптимальна програма#1756

Оптимальна програма

1 секунда

64 мегабайти

Легка

Як відомо, написання програм часто є зовсім не простим завданням. Ситуація стає ще складнішою, якщо ваші програми мають працювати якомога швидше. А іноді для цього є вагома причина. У багатьох великих програмах, таких як операційні системи чи бази даних, існують "вузькі місця" — ділянки коду, які виконуються знову і знову, і складають значну частку загального часу виконання. Зазвичай має сенс переписати такі частини коду мовою асемблера, оскільки навіть незначне скорочення часу виконання матиме велике значення, якщо код виконується мільярди разів.

У цій задачі ми розглядатимемо завдання автоматизації генерації оптимального асемблерного коду. Дано функцію (описану серією пар вхід/вихід); ви повинні скласти найкоротшу програму на асемблері, яка обчислює цю функцію.

Ваша програма має працювати на стековій машині, що підтримує лише п'ять команд: ADD, SUB, MUL, DIV та DUP. Перші чотири команди знімають два верхніх елементи зі стеку та кладуть на стек їхню суму, різницю, добуток або цілу частку відповідно. Команда DUP кладе на стек копію верхнього елемента.

Якщо команди застосовуються до стека з двома верхніми елементами $a$ і $b$ (де $b$ — верхній), отримуємо такі результати:

На початку виконання програми стек містить одне ціле число — вхідне. Після завершення обчислення також у стеці має залишитись лише одне ціле число — результат обчислення.

Стекова машина переходить у стан помилки у трьох випадках:

Спроба виконати команду DIV, якщо верхній елемент стека дорівнює $0$ .
Спроба виконати команду ADD, SUB, MUL або DIV, якщо у стеці присутній лише один елемент.
Операція призводить до значення, що по модулю перевищує $30000$ або менше $- 30000$ .

Вхідні дані

Вхід складається з кількох описів функцій. Кожен опис починається рядком, що містить одне число $n$ ( $n \leq 10$ n \leq 10) — кількість пар вхід/вихід. Два наступні рядки містять по $n$ цілих чисел: перший рядок — вхідні значення (усі різні), другий — відповідні вихідні. Всі числа за модулем не перевищують $30000$ .

Вхід закінчується описом з $n = 0$ n = 0. Цей тестовий випадок не слід опрацьовувати.

Вихідні дані

Ви маєте знайти найкоротшу програму, яка реалізує функцію $f$ , таку що $f (x_{i}) = y_{i}$ f(x_i) = y_i для всіх $i \in {1, \dots, n}$ i \in \{1, \ldots, n\}. Це означає, що програма не повинна переходити у стан помилки при виконанні на заданих вхідних $x_{i}$ x_i, хоча для інших вхідних такого вимагати не потрібно. Розглядайте лише програми, що містять не більше $10$ команд.

Для кожного опису функції спочатку виведіть номер опису. Потім виведіть послідовність команд, що складають найкоротшу програму для обчислення заданої функції. Якщо існує декілька таких програм, виведіть лексикографічно найменшу. Якщо програми довжиною не більш як $10$ команд не існує, що обчислює дану функцію, виведіть рядок "Impossible". Якщо найкоротша програма містить нуль команд, виведіть "Empty sequence".

Після кожного тесту виводьте порожній рядок.

Приклади

Приклад 1