Optimal Programs
题目描述
众所周知，编写程序通常并不容易。如果程序需要尽可能快，事情就会变得更加困难。有时这是有必要的。许多大型程序（如操作系统或数据库）存在“瓶颈”——那些被反复执行的代码段，占据了总运行时间的很大一部分。此时，通常需要用汇编语言重写该部分代码，因为即使运行时间的小幅提升，在代码执行数十亿次时也会产生显著影响。
在本问题中，我们将考虑自动生成最优汇编代码的任务。给定一个函数（以一系列输入/输出对的形式），你需要编写一个最短的汇编程序来计算该函数。
你编写的程序将运行在一个基于栈的机器上，该机器仅支持五种指令：ADD、SUB、MUL、DIV 和 DUP。前四条指令从栈中弹出最顶部的两个元素，并将它们的和、差、积或整数商（分别对应）压入栈中。DUP 指令将栈顶元素的额外副本压入栈中。
例如，如果对栈顶的两个元素 a 和 b 应用这些指令，结果栈如下所示：
| 指令 | 栈变化（从左到右：栈顶在右） |
|---|---|
| ADD | ..., a, b → ..., (a + b) |
| SUB | ..., a, b → ..., (a - b) |
| MUL | ..., a, b → ..., (a * b) |
| DIV | ..., a, b → ..., (a / b) |
| DUP | ..., a → ..., a, a |
程序执行开始时，栈中仅包含一个整数：输入值。计算结束时，栈中也必须仅包含一个整数，该数字即为计算结果。
在以下三种情况下，栈机器会进入错误状态：
- 执行
DIV指令时，栈顶元素为 0。 - 执行
ADD、SUB、MUL或DIV指令时，栈中只有一个元素。 - 操作产生的值绝对值超过 30000。
输入
输入由一系列函数描述组成。每个描述的第一行是一个整数 n（n <= 10），表示接下来的输入/输出对数。接下来的两行各包含 n 个整数：第一行是 x1, x2, ..., xn（所有 xi 均不同），第二行是 y1, y2, ..., yn。这些数字的绝对值不超过 30000。
输入以 n = 0 的测试用例结束，该用例不应被处理。
输出
你需要找到一个最短的程序，计算函数 f，使得对于所有 1 <= i <= n，f(xi) = yi。这意味着你输出的程序在输入 xi 上执行时不能进入错误状态（尽管在其他输入上可能出错）。只需考虑最多 10 条指令的程序。
对于每个函数描述，首先输出描述编号。然后输出构成最短程序的指令序列。如果有多个最短程序，输出字典序最小的那个。如果不存在不超过 10 条指令的程序，输出 Impossible。如果最短程序是空序列，输出 Empty sequence。
每个测试用例后输出一个空行。
示例输入 1
4
1 2 3 4
0 -2 -6 -12
3
1 2 3
1 11 1998
1
1998
1998
0
示例输出 1
Program 1
DUP DUP MUL SUB
Program 2
Impossible
Program 3
Empty sequence
来源
1998 年西南欧区域赛（Southwestern European Regional Contest）