#P4365. [IOI2014]gondola缆车
[IOI2014]gondola缆车
[IOI 2014] Gondola 缆车
题目描述
猫空缆车系统有一条环形轨道和一个车站。轨道上最初有 辆缆车,编号为 。若编号 的缆车经过车站,则接下来是缆车 ;缆车 之后是缆车 。
缆车故障时,用编号最小的尚未使用过的备用缆车原地替换。备用缆车的编号依次为 ,故障缆车不会重新使用。
你到车站后,记录连续经过车站的一整圈缆车,共 个编号。观察期间不发生故障;到达前可以已经发生任意次故障。这样得到的序列称为缆车序列。同一种轨道状态从不同缆车开始观察可以得到不同序列。比如 时,若从未发生故障, 与 均可出现, 则不能出现。
把每辆发生故障的缆车的编号按故障先后列出,得到替换序列。若依序发生这些故障之后可以观察到某个缆车序列,就称这个替换序列生成了该缆车序列。
例如 时依次更换下列缆车,替换序列为 。
| 故障缆车 | 新缆车 | 一种可观察到的缆车序列 |
|---|---|---|
| 1 | 6 | |
| 4 | 7 | |
| 7 | 8 |
输入格式
第一行一个整数 ,用于指定本次输入要求完成的任务。第二行一个整数 。第三行 个整数 ,表示给定的序列。
输出格式
- :判断给定序列是否为缆车序列。若是,输出 ;否则输出 。
- :给定序列一定是缆车序列。构造任意一个能够生成它的替换序列,输出一行:先输出长度 ,再依顺序输出这 个故障编号。没有故障时只输出 。
- :输出能生成给定缆车序列的替换序列数量,对 取模。如果给定序列不是缆车序列,则输出 ;如果合法且没有发生过故障,则输出 。
样例
样例输入 #1
1
30
16 26 18 19 20 13 22 21 24 25 17 27 28 29 30 1 2 3 11 5 6 8 7 9 10 12 4 23 14 15
样例输出 #1
0
样例输入 #2
6
2
3 4
样例输出 #2
2 1 2
这个样例也可以输出 2 2 1。更换完成后,两种方案都可以通过选择合适的起始缆车,观察到 。
原赛的其他示例如下。
| 输入序列 | 结果 | 说明 | |
|---|---|---|---|
| 1 | 初始顺序 | ||
| 从缆车 开始 | |||
| 缆车 不会紧接着到缆车 | |||
| 缆车 不会紧接着到缆车 | |||
| 2 | 编号 重复 | ||
| 3 | 替换序列可以是 | ||
| 缆车 不会紧接着到缆车 | |||
| 4 | 1 2 |
依次输出长度及故障编号 | |
0 |
无故障记录 | ||
| 5 | 2 5 8 |
依次输出长度及故障编号 | |
| 7 | 替换序列为 或 | ||
| 8 | 替换序列为 | ||
| 9 | 编号重复 | ||
| 10 | 替换序列为 或 |
数据范围
保证 。
| 的范围 | 序列限制 | |
|---|---|---|
| 1 | 到 各出现一次 | |
| 2 | ||
| 3 | ||
| 4 | ||
| 5 | ||
| 6 | ||
| 7 | ||
| 8 | ,至少有 辆初始缆车没有发生故障 | |
| 9 | ||
| 10 |