UVA12666 疯狂的谜题 Killer Puzzle
题目描述
> 你有没有做过下面这个疯狂的谜题？
>
> 请回答下面 10 个问题，各题都恰有一个答案是正确的。
>
> 1. 第一个答案是 B 的问题是哪一个？
> A.2 B.3 C.4 D.5 E.6
> 2. 恰好有两个连续问题的答案是一样的，它们是：
> A.2,3 B.3,4 C.4,5 D.5,6 E.6,7
> 3. 本问题答案和哪一个问题的答案相同？
> A.1 B.2 C.4 D.7 E.6
> 4. 答案是 A 的问题的个数是：
> A.0 B.2 C.4 D.7 E.6
> 5. 本问题答案和哪一个问题的答案相同？
> A.10 B.9 C.8 D.7 E.6
> 6. 答案是 A 的问题的个数和答案是什么的问题的个数相同？
> A.B B.C C.D D.E E.以上都不是
> 7. 按照字母顺序，本问题的答案和下一个问题的答案相差几个字母？
> A.4 B.3 C.2 D.1 E.0
> 8. 答案是元音字母的问题的个数是：
> A.2 B.3 C.4 D.5 E.6
> 9. 答案是辅音字母的问题的个数是：
> A.一个质数 B.一个阶乘数 C.一个平方数 D.一个立方数 E.5 的倍数
> 10. 本问题的答案是：
> A.A B.B C.C D.D E.E
>
> **注意**：
> 1. 你的答案不能自相矛盾。例如，第一题的答案不能是 B。
> 2. 你需要确保每道题的选项中只有你的答案是正确的，其他都是错误的。例如，只要问题 5 的答案是 A，那么问题 6,7,8,9 的答案都不能是 A。
> 3. 你需要确保每道题目都是有效的。例如，若问题 2 和问题 3 的答案相同，且问题 8 和问题 9 的答案也相同，则问题 2 是非法的，因为并不是恰好有两个连续问题的答案一样。
这道题目当然可以手算，但是作为程序员，编程求解会更有意思。
**编程求解**。最容易想到的方法就是穷举法，即考虑所有 $5^{10}=9765625$ 种可能，依此验证答案是否合法（即每道题有且只有你的答案是正确的）。伪代码如下：
```python
for all(answer_list):
bad = False
for testing_question in [1,2,3,4,5,6,7,8,9,10]:
for testing_option in ["a","b","c","d","e"]:
# 你的答案必须得是正确的
if testing_option == answer_list[testing_question] and check(testing_question, testing_option) == False:
bad = True
# 其他答案得是错误的
if testing_option != answer_list[testing_question] and check(testing_question, testing_option) == True:
bad = True
if not bad:
print answer_list
```
这里 `answer_list` 是一个字符列表，下标从 $1$ 开始，第 $i$ 个字符指代第 $i$ 个问题的答案。
不论你相不相信，满足以上问题的唯一 `answer_list` 是 `cdebeedcba`。
现在，我们要写个更通用的程序来求解类似以上问题的全部问题，而前提是先形式化的描述这些问题。
**问题的形式化描述**。本问题使用 Lisp 方言来解决这些全部的问题。Lisp 看上去有些特别，例如 C++/Java 的函数 `f(a,b)` 在 Lisp 中写作 `(f a b)`。类似地，C++/Java 中的 `f(a,g(b,c),d)` 在 Lisp 中写作 `(f a (g b c) d)`。下面是一个描述题目的例子：
```plaintext
3. (equal (answer 3) (answer (option-value)))
a. 1
b. 2
c. 4
d. 7
e. 6
```
这里有两个重要的内置函数：
|函数|功能|
|:-:|:-:|
|`(answer idx)`|返回 `answer_list[idx]`（就像上文伪代码中显示的）。|
|`(option-value)`|返回该题目被选中的项所代表的表达式的计算结果。|
例如上面的题目中，如果我们选 `c`，那么 `(option-value)` 所返回的就是整数 $4$。当然选项可能不只是数字，可以参考样例。
而函数 `check(testing_question, testing_option)` 可以被描述成以下这样：
1. 设置函数 `(option-value)`，使之返回 `testing_option` 所代表的表达式的计算结果。
2. 计算 `(testing_question)` 对应的题目的表达式。
3. 如果计算过程中抛出了未被处理的异常，则返回 `False`。
4. 如果计算出的结果是布尔类型，则返回之；否则还是返回 `False`。
有一种特殊的选项值叫做 `"none-of-above"`，意为“以上选项都不正确”，其选择取决于其他选项怎么选：当一道题被选为 `"none-of-above"` 时，意味着其他选项对应的表达式计算结果都为 `False`。本题中，每道题目最多只有一个选项为 `"none-of-above"`，并且只会出现在每道题目的最后一个选项。
## 细节
这里有一些 Lisp 方言的细节。
+ 有 $4$ 种类型的数据：整数、字符串、布尔和函数。
+ 只有 $2$ 种布尔类型的值：真或者假。当然，这里不存在布尔常量的形式化描述，既不像 `#t` 和 `#f`（于 Scheme 之中），也不像 `t` 和 `nil`（于 Common Lisp 之中）。
+ 整数永远非负。
+ 字符串被双引号包裹，例如 `"a string"`。
+ 没有变量，此后这些被称作「标识符」，为预定义函数。
以下是一份预定义函数的列表。`!` 开头的函数可能会抛出异常而 `@` 开头的函数可能会处理异常。就像 C++ 语言一样，若一个异常被抛出，整个程序进程将终止直到异常被处理。
### 基础函数
|函数|功能|
|:-:|:-:|
|`(equal a b)`|当且仅当 `a` 和 `b` 的类型和值都相等时返回 `True`，否则返回 `False`。在本问题中，你不需要比较两个函数。|
|`(option-value)`|功能如前所述。|
|`!(answer idx)`|功能如前所述，但当 `idx` 的值并非 $1 \sim n$ 之间的整数（$n$ 即问题个数），则抛出异常。|
|`!(answer-value idx)`|返回 `answer_list[idx]` 对应的项所代表的表达式的计算结果，抛出异常的条件同上。|
### 谓词
谓词是一种特殊的函数，其接受一个任意类型参数并返回一个布尔值。
|函数|功能|
|:-:|:-:|
|`prime-p`|当且仅当这个参数是个正质数时返回 `True`。|
|`factorial-p`|当且仅当这个参数是某个整数的阶乘时返回 `True`。|
|`square-p`|当且仅当这个参数是某个整数的平方时返回 `True`。|
|`cubic-p`|当且仅当这个参数是某个整数的立方时返回 `True`。|
|`vowel-p`|当且仅当这个参数为字符串，只有单个字母并且这个字母是元音字母时返回 `True`。|
|`consonant-p`|当且仅当这个参数为字符串，只有单个字母并且这个字母是辅音字母时返回 `True`。|
### 统计与算术
|函数|功能|
|:-:|:-:|
|`!@(first-question pred)`|返回第一个满足谓词 `pred` 的题目编号。如果不存在这样的题目则抛出异常。|
|`!@(last-question pred)`|功能同上，但返回的是最后一个满足谓词 `pred` 的题目编号。|
|`!@(only-question pred)`|返回唯一满足谓词 `pred` 的题目编号，如果有多个题目满足或没有题目满足则抛出异常。|
|`@(count-question pred)`|返回满足谓词 `pred` 的题目个数。|
|`!(diff-answer idx1 idx2)`|返回题目 `idx1` 与 `idx2` 的答案的字母编号之差。当 `idx1` 或 `idx2` 不在有效范围内时抛出异常（同函数 `(answer idx)` 抛异常的条件），否则返回 $0\sim m-1$ 之间的整数，其中 $m$ 是题目的选项个数。|
注意：在前四个以 `@` 开头的函数中，如果计算谓词时抛出了异常，则异常会被处理，且该谓词被视为不满足。例如，当 `answer_list="abc"` 时，`(count-question (make-answer-diff-next-equal 0))` 返回 $0$ 并且不抛出异常，尽管计算 `((make-answer-diff-next-equal 0)3)` 时会抛出异常。然而，其他函数并不会处理异常，例如当 $n=3$ 时（即只有 $3$ 个问题时），`(factorial-p (answer-value 5))` 会抛出异常而非返回 `False`。
### 谓词生成器
当然也有生成（更正确地说，合并）谓词的函数：
|函数|功能|
|:-:|:-:|
|`!(make-answer-diff-next-equal num)`|返回谓词 `(p idx)`，判断 `(diff-answer idx idx+1)` 是否等于 `num`。当 `num` 不是整数的时候抛出异常。|
|`(make-answer-equal a)`|返回谓词 `(p idx)`，判断 `(answer idx)` 是否等于 `a`。|
|`(make-answer-is pred)`|返回谓词 `(p idx)`，判断 `(answer idx)` 是否满足谓词 `pred`。|
|`(make-answer-value-equal a)`|和 `make-answer-equal` 类似，但调用的是 `(answer-value idx)`。|
|`(make-answer-value-is pred)`|和 `make-answer-is` 类似，但调用的是 `(answer-value idx)`。|
|`!(make-is-multiple num)`|返回一个谓词 `(p i)`，当且仅当 `num` 是整数且 `i` 是 `num` 的整数倍时返回 `True`。当 `num` 不是整数时抛出异常。|
|`!(make-equal val)`|返回谓词 `(p v)`，该谓词会返回 `(equal v val)` 的结果。当 `val` 既不是整数也不是字符串时抛出异常。|
|`(make-not pred)`|返回谓词 `(p v)`，当且仅当 `(pred v)` 为 `False` 的时候返回 `True`。|
|`(make-and pred1 pred2)`|返回谓词 `(p v)`，当且仅当 `(pred1 v)` 和 `(pred2 v)` 都为 `True` 时返回 `True`。请注意短路求值操作是不允许的。|
|`(make-or pred1 pred2)`|返回谓词 `(p v)`，当且仅当 `(pred1 v)` 和 `(pred2 v)` 至少有一个为 `True` 时返回 `True`。请注意短路求值操作是不允许的。|
例如，`(make-is-multiple 3)` 返回谓词「某值是 $3$ 的倍数」，所以 `((make-is-multiple 3) 6)` 返回 `True`，而 `((make-is-multiple 3) 10)` 返回 `False`。而 `(make-not (make-or square-p prime-p))` 返回谓词「某值既不是平方数也不是质数」。
输入格式
有最多 $50$ 组测试数据。对于每组测试数据：
- 输入的第一行包含两个整数 $n$ 和 $m$，其意义已在上边解释过（$n$ 为问题数目而 $m$ 为选项个数）。
- 每个问题由 $m+1$ 行描述，第一行为问题的表达式，后 $m$ 行为选项的表达式，最后跟一个空行。问题被标号为整数 $1\sim n$ 而选项被标记为 `a` 到 `e`。
保证选项为合法的表达式且不可能是 `option-value`（如果真是这样，那么会引起无限递归，这题也没法做了）。保证数据强度不太高，即大多数测试数据的规模足够小。
输出格式
对于每组测试数据，第一行输出 `Case x:`，其中 `x` 为测试数据的编号；接下来若干行是所有可能的答案，按字典序排序。数据保证至少有一组解。