UVA656 Optimal Programs

众所周知，编程一般不是一件容易的事。如果要求你的程序尽可能的快，事情就更复杂了。然而，有时这种要求是有道理的。一些大型的程序或项目，例如操作系统和数据库，有“瓶颈”：不断被执行的一小段程序，总体的运行时间中占据相当的比例。因此，用汇编语言重写这（些）部分是值得的，因为，即使优化的不多，如果代码被执行成千上万次，最后也可以节省很长时间。 在这道题里面，我们尝试将生成最优的汇编代码的过程自动化。即，给定一个函数（通过一系列对应的输入/输出，具体格式见下文），你需要给出最短的“汇编”代码。 本题里的“汇编”代码基于栈结构，有且仅有以下 5 个指令：ADD（加），SUB（减），MUL（乘），DIV（整除，类似于C++的`/`或Python的`//`），DUP（复制）。前四种指令对应四则运算，从栈中弹出栈顶的2个数，并将运算结果压栈；最后一种将栈顶的元素复制。 如果将该命令作用于一个如左图所示的栈，将 $a,b$ 压入栈，进行不同操作的结果如下： ```plain 初始栈 ADD SUB MUL DIV DUP | | | | | | | | | | | a | | a | | | | | | | | | | a | | b | |b+a| |b-a| |b*a| |b/a| | b | | c | | c | | c | | c | | c | | c | +---+ +---+ +---+ +---+ +---+ +---+ ``` 在程序的开始，栈中只有一个元素，即程序的输入。程序结束时，栈中应该只有一个元素，即程序的输出，也是计算的结果。 以下 3 种情况程序会报错： - 在 DIV（整除）命令中除数为0 - 在栈中仅有 1 个元素时进行 ADD（加）、SUB（减）、MUL（乘）、DIV（整除）命令 - 运算的某一时刻栈中有元素的绝对值超过 30000

输入有多组数据。 对于每组子数据： 第一行，一个整数 $n(n\le 10)$。 第二行是 $n$ 个互不相同的整数 $x_1,x_2,\dots ,x_n$，表示程序的输入。 第三行同样是 $n$ 个整数 $y_1,y_2,\dots ,y_n$，$y_i$ 为程序在输入 $x_i$ 时的输出。 **数据保证 $x_i,y_i$ 的绝对值均小于30000** 输入以 $n=0$ 结束。

你需要找到最短的函数 $f$ ，使得对于所有的 $1 \le i \le n$，均有 $f(x_i)=y_i$。注意，你的程序对于所有指定的输入不能报错（但在输入清单外的有可能报错）。注意，程序的长度最大是 10。 对于每组子数据，首先输出 `Program k`（意为“第 $k$ 个程序”），其中 $k$ 是子数据的ID（从1开始）。随后输出满足条件的最短程序。如有多组同样短的，输出字典序最小。如果不能用10条语句及以下的程序实现，输出 `Impossible` （意为“不可能”）。如果存在可以不用处理直接输出的情况（即可以用 0 条语句实现），输出 `Empty Sequence` （意为“序列为空”）。 #### 样例解释 第一组子数据相当于 $f(x)=x-x^2$ ，可用 `DUP DUP MUL SUB` 解决。 不存在能在 10 条语句以内解决第二组子数据的。 第三组子数据可以用一个空程序解决。