所谓机械娃娃,是能够自动地重复特定运动序列的娃娃。在日本,很多机械娃娃在古代就造出来了。机械娃娃的运动被一个由多个器件组成的管路所控制。这些器件通过管道连在一起。每个器件都有一个或两个出口,而且可以有任意多的(也可以为零)的入口。每个管道都从某个器件的出口连到同一器件或其他器件的入口。每个入口都连接恰好一个管道,而每个出口也都连接恰好一个管道。
为了描述娃娃是如何运动的,设想有一个球放在这些器件之一的上面。这个球在管路中穿行。在穿行的每一步,它从所在器件的一个出口离开该器件,沿着连接该出口的管道,进入管道另一头所连接的器件。
器件有三种类型:起点、 触发器和开关。总共有恰好一个起点,
起点是球最初所在的那个器件。它有一个出口。它的序列号是
一旦球进入某个触发器,就会让娃娃做某个特定运动。每个触发器都有一个出口。触发器的序列号是从
每个开关都有两个出口,被记为“X”和“Y”。开关的状态或者为“X”,或者为“Y”。在球进入
某个开关后,它会从开关的当前状态所对应的出口离开。此后开关将切换为另一状态。最初,所有开
关的状态都是“X”。开关的序列号是从
告诉你触发器的数量
- 球在若干步之后返回到起点。
- 当球首次返回到起点时,所有开关的状态都是“X”。
- 在球首次返回到起点时,此前它进入所有触发器的总次数恰好为
。这些被进入过的触发器,其序列号按照被球经过的顺序依次为 。 - 设
为球首次返回到起点时,球所引起的所有开关状态切换的总次数。 不能超过 。
同时,你不要用太多的开关。
实现细节
你需要实现下面的过程。
create_circuit(int M, int[] A)
M
:触发器数量。A
:长度为 的数组,其中按照球进入的顺序,给出了被进入的触发器的序列号。- 该过程将被调用恰好一次。
- 注意,
的值是数组 的长度,你可以按照注意事项中的有关内容来取得。
你的程序需要调用下面的过程来作答。
answer(int[] C, int[] X, int[] Y)
C
:长度为 的数组。器件 ( )的出口被连到器件C[i]
。X, Y
:长度相同的两个数组。这些数组的长度 为开关的数量。对于开关 ( )来说,其出口“X”被连到器件X[j - 1]
,而出口“Y”被连到器件Y[j - 1]
。C
、X
和Y
中的任一元素必须是 到 的整数(包括 和 )。 最多只能是 。- 必须调用该过程恰好一次。
- 由
C
、X
和Y
所表示的管路必须满足题面中的限制条件。
如果上述条件不满足,你的程序将被判为
例子
假设 create_circuit(4, [1, 2, 1,
3])
。
上图展示了函数调用answer([1, -1, -2, 0, 2], [2, -2], [3, 1])
所对应的管路图。图中的数字是器件的序列号。
图中使用了两个开关。所以
开关
球的穿行轨迹如下:
当球首次进入开关
当球第二次进入开关
球在经过触发器
在压缩附件包中,有一个文件 sample-01-in.txt
对应于本例。其他输入样例也可以在压缩附件包中找到。
在样例数据下载中的文件ex_doll1.in
对应于本例。其他的输入样例在样例包中还可找到。注意:样例包中的输出没有任何意义。
限制条件
子任务
每个测试样例的分数和限制条件如下:
- (2 分)对每个
( ),整数 在序列 中最多出现 次。 - (4 分)对每个
( ),整数 在序列 中最多出现 次。 - (10 分)对每个
( ),整数 在序列 中最多出现 次。 - (10 分)
- (18 分)
- (56 分)无附加限制
对每个测试样例,如果你的程序被判定为
- 如果
,你将获得该测试样例的满分。 - 对于子任务
和 的每个测试样例,如果 ,你将获得部分分。该测试样例上的得分为 ,再乘以该子任务的满分分数。 - 否则,得分为
。
注意,你在每个子任务上的得分是该子任务中所有测试样例上的最低得分。
请注意:在测试中,如果你的程序在一个子任务中某个点未获得满分,则可能会得到
评测程序示例
评测程序示例按照以下格式从标准输入中读入输入:
- 第
行: - 第
行:
评测程序示例产生三个输出。
首先,评测程序示例把你的答案以下列格式输出到文件out.txt
。
- 第
行: - 第
行( ):C[i]
- 第
行( ):X[j - 1] Y[j - 1]
其次,评测程序示例模拟球的移动。它把该球经过的器件的序列号,按照经过顺序输出到文
件log.txt
。
第三,评测程序示例将在标准输出中打印对你的答案的评价
- 如果你的程序被判为
,评测程序示例按照以下格式打印 和 : - 如果你的程序被判为
,它打印 。各类 的含义如下:answered not exactly once
:过程answer
不是恰好被调用一次。wrong array length
:C
的长度不是 ,或者X
和Y
的长度不一样。over 400000 switches
: 大于 。wrong serial number
:C
、X
或者Y
的某个元素比 小或者比 大。over 20000000 inversions
:球没有在所有开关的状态变化总数超过 之前返回到起点。state 'Y'
:当球首次返回到起点时,某个开关的状态为“Y”。wrong motion
:触发运动的触发器和序列 所列的不一致。
注意,当你的程序被判为 out.txt
和/或log.txt
。
约定及限制
对于所支持的各种编程语言,下面列出了对应的数据类型。对于数据类型的细节等,参见实现示例。
语言 | 数组 |
||||
---|---|---|---|---|---|
时间限制:
空间限制: