精灵程序员小 和 小 拥有无限的寿命,因此在写代码之余,它们经常玩一些对抗游戏来打发时间。尽管如此,时间还是太多,于是它们发明了一款专用于消磨时间的游戏:最长待机。
为了了解最长待机的规则,首先要了解精灵们使用的编程语言 Sleep++ 的规则:
-
程序由 个函数组成,第 个函数具有种类 和子函数编号序列 。 可以为空,此时 为 。
-
以及所有的 和 可以由程序员任意给出,但它们需要满足以下所有条件:
- ;
- ,;
- , 中元素两两不同且均为 中的整数;
- ,恰好有一个 包含了 。
-
调用函数 时,按顺序执行如下操作:
- 若 ,令变量 为 ;否则程序员需要立即为 输入一个正整数值。
- 若 为空,程序等待 秒;否则重复以下操作 次:
-
若一个种类为 的函数 被调用多次,则其每次调用都需要输入 。
-
我们认为,在函数调用中,除了“等待 秒”之外的操作不消耗任何时间,即函数调用、运行和输入都在瞬间完成。因此,一个时刻内程序员可能输入多个数。
可以证明,调用任意一个 Sleep++ 程序的任意一个函数,无论如何设定输入,消耗的时间总是有限的。
“最长待机”的游戏规则如下:
-
小 和 小 准备好各自的 Sleep++ 程序并选择各自程序中的一个函数。它们互相知晓对方程序的结构以及选择的函数。
-
在时刻 ,小 和 小 同时调用自己选择的函数,游戏开始。
-
在时刻 (),双方可以看到对方在时刻 至 输入的所有数字,并相应调整自己在时刻 输入的数字,但双方无法得知对方在时刻 输入的数字。
-
函数调用先结束的一方输掉游戏,另一方胜利。两个调用同时结束算作平局。
小 和 小 都是绝顶聪明的,在它们眼中,如果有一方存在必胜策略,那么这局游戏是不公平的。换言之,双方都不存在必胜策略的游戏是公平的。
小 写了一个 个函数的 Sleep++ 程序并进行了 次操作,操作有以下两种:
- 操作一:给出 ,将 修改为 ;
- 操作二:给出 ,与小 玩一局“最长待机”,开始时小 会调用自己的函数 。
小 信奉极简主义,它希望对于每一局游戏设计出函数个数最少的程序,使得选择其中某个函数能让这局游戏是公平的。你能帮它求出最少所需的函数个数吗?
可以证明,小 总是能设计一个程序并选择其中一个函数,使得游戏是公平的。