Оптимальная программа
Как вы знаете, написание программы, дело зачастую далеко не такое простое, как может показаться. И этот процесс становится еще труднее, если ваши программы должны работать как можно быстрее. А иногда есть веские основания, чтобы они были быстрыми. У многих крупных программных кодах, такие как операционные системы и базы данных, есть "узкие места" - сегменты кода, которые будут выполняться снова и снова, и "пожирать" значительную часть от общего времени работы. Как правило, эту часть кода приходится переписывать на ассемблере, потому что даже небольшая экономия времени работы будет очень важна, особенно если код выполняется миллиарды раз.
В этой задаче мы будем рассматривать задачу автоматизации генерации оптимального ассемблерного кода. Для заданных функций (в виде ряда входных/выходных пар), вы должны придумать кратчайшую программу, которая вычисляет эти функции.
Ваша программа будет работать на основе стековой машины, которая поддерживает только пять команд: 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".
Выводите пустую строку между разными тестовыми случаями.