精灵程序员小
为了了解最长待机的规则,首先要了解精灵们使用的编程语言 Sleep++ 的规则:
程序由
个函数组成,第 个函数具有种类 和子函数编号序列 。 可以为空,此时 为 。 以及所有的 和 可以由程序员任意给出,但它们需要满足以下所有条件: ; , ; , 中元素两两不同且均为 中的整数; ,恰好有一个 包含了 。
调用函数
时,按顺序执行如下操作:- 若
,令变量 为 ;否则程序员需要立即为 输入一个正整数值。 - 若
为空,程序等待 秒;否则重复以下操作 次:- 按顺序调用编号为
的函数。
- 按顺序调用编号为
- 若
若一个种类为
的函数 被调用多次,则其每次调用都需要输入 。我们认为,在函数调用中,除了“等待
秒”之外的操作不消耗任何时间,即函数调用、运行和输入都在瞬间完成。因此,一个时刻内程序员可能输入多个数。
可以证明,调用任意一个 Sleep++ 程序的任意一个函数,无论如何设定输入,消耗的时间总是有限的。
“最长待机”的游戏规则如下:
小
和 小 准备好各自的 Sleep++ 程序并选择各自程序中的一个函数。它们互相知晓对方程序的结构以及选择的函数。在时刻
,小 和 小 同时调用自己选择的函数,游戏开始。在时刻
( ),双方可以看到对方在时刻 至 输入的所有数字,并相应调整自己在时刻 输入的数字,但双方无法得知对方在时刻 输入的数字。函数调用先结束的一方输掉游戏,另一方胜利。两个调用同时结束算作平局。
小
小
- 操作一:给出
,将 修改为 ; - 操作二:给出
,与小 玩一局“最长待机”,开始时小 会调用自己的函数 。
小
可以证明,小
输入格式
输入的第一行包含两个正整数
接下来
- 前两个整数
表示函数种类和子函数编号序列长度; - 接下来
个整数 描述子函数编号序列。
接下来
输出格式
对于每个操作二输出一行一个整数,表示小
样例 #1
样例输入 #1
3 6 0 2 2 3 0 0 0 0 2 1 1 3 2 1 1 3 1 2 2 1
样例输出 #1
3 3 1
提示
【样例 1 解释】
对于前两次游戏,小
可以给出与小 完全一致的程序并在游戏开始时调用函数 。可以证明不存在函数个数更少的方案。对于第三次游戏,小
可以给出一个仅包含一个种类为 的函数的程序,并在游戏开始时调用函数 。- 在时刻
,小 输入其程序中的 ,小 输入其程序中的 。- 注意:
变量在小 和小 的程序之间是独立的,不会互相影响。
- 注意:
- 输入完成后,小
的程序在时刻 结束,小 的程序在时刻 结束。 - 由于两人在时刻
互不知道对方的决策,不能保证 和 的大小关系,故双方均不存在必胜策略,这局游戏是公平的。
- 在时刻
【样例 2】
见附件中的 sleep2.in/ans
。
该组数据满足特殊性质 AD。
【样例 3】
见附件中的 sleep3.in/ans
。
该组数据满足特殊性质 BD。
【样例 4】
见附件中的 sleep4.in/ans
。
该组数据满足特殊性质 D。
【样例 5】
见附件中的 sleep5.in/ans
。
该组数据满足特殊性质 C。
【子任务】
对于所有测试数据,
, ; , ,$0 \le l_i , ; , ; ,恰好有一个 包含了 ; , , 。
测试点编号 | 特殊性质 | ||
---|---|---|---|
无 | |||
AD | |||
BD | |||
D | |||
AD | |||
BD | |||
D | |||
A | |||
BC | |||
B | |||
C | |||
无 | |||
A | |||
BC | |||
B | |||
C | |||
无 |
特殊性质 A:保证
- 任意时刻
均为 ; , ;- 操作二的
均为 。
特殊性质 B:保证
- 操作二的
满足当时的 为 。
特殊性质 C:保证
, ; ,序列 单调递增。
特殊性质 D:保证
- 操作二不超过
个; - 操作二的
均为 。
时间限制:2s
空间限制: