茜塔与世界线悖论
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目背景
在快要沉没的世界里,茜塔是一个碰到墙就会向左转的小女孩。她拾起了一把能够分裂自身概率的叉子——概率之叉。从那以后,前方的路不再只有一种可能。
分裂从茜塔自身延伸到箱子,再到整个宇宙。世界线不断分岔、交织,编织出比单个宇宙更广阔的图景。那些看似尚未发生的可能,也许早已藏在世界的规则之中,等待她发现。
但可能性的存在,并不意味着每一种未来都能抵达。茜塔面对一份当前世界线的记录,以及一份她希望抵达的目标记录。她必须遵循世界的局部变换规则,让两份记录完全一致。
她想知道:通向那个未来的路是否存在?如果存在,最少要走多少步?
题目描述
一条世界线由 个记忆节点组成,节点从左到右编号为 到 。每个节点的状态为 或 。你将获得每个节点的初始状态和目标状态。
茜塔可以借助概率之叉改变局部的记录。每次,她可以选择三个连续的节点,按从左到右的顺序读取它们的状态,并执行以下任意一种变换:
- 将
001变为100,或将100变为001; - 将
110变为011,或将011变为110。
所选三个节点的状态必须符合对应的变换规则。每次变换计为一次操作,其他节点的状态保持不变。茜塔可以进行任意多次操作,每次可以重新选择三个连续的节点。
请计算,从初始状态出发,使所有节点的状态都与各自的目标状态一致,至少需要多少次操作。
如果无法做到,输出 ;若初始状态已经与目标状态完全一致,输出 。
输入格式
第一行输入一个整数 ,表示记忆节点的数量。
接下来 行,每行输入两个整数,均为 或 。
第 行的第一个整数表示编号为 的节点的初始状态,第二个整数表示该节点的目标状态。
输出格式
输出一行,包含一个整数,表示最少操作次数;如果无法到达目标世界线,则输出 。
样例
4
0 0
1 0
0 0
0 1
1
6
1 0
1 0
0 0
0 0
0 1
0 1
4
4
0 0
1 0
0 1
0 0
-1
样例说明
样例 1
初始状态为 0100,目标状态为 0001。
选择编号为 的节点,将 100 变为 001,即可到达目标世界线。
样例 2
初始状态为 110000,目标状态为 000011。
一种操作过程为:
110000 → 011000 → 001100 → 000110 → 000011
上述每一步都将一个连续片段 110 变为 011。
可以证明,至少需要 次操作。
样例 3
初始状态为 0100,目标状态为 0010。
无法通过题目允许的操作完成转换。
数据范围与部分分
对于所有测试数据,保证:
- ;
- 每个节点的初始状态和目标状态均为 或 。
本题采用 IOI 部分分制,共 个子任务,每个子任务包含 个测试点。
| 子任务 | 分值 | 附加限制 |
|---|---|---|
| 分 | ||
| 无附加限制 |
各子任务独立计分。只有通过一个子任务的全部测试点,才能获得该子任务的分数。