#P17580. [JAG 2026 Summer Camp #3] JAG City Marathon II
[JAG 2026 Summer Camp #3] JAG City Marathon II
题目描述
Just A Grid City(简称 JAG City)有 条水平道路和 条竖直道路。这些道路构成一个正方形网格。任意两条相邻的平行道路之间的距离为 。水平道路从上到下编号为 到 ,竖直道路从左到右编号为 到 。我们将第 条水平道路与第 条竖直道路的交点称为 。
JAG City 将在这些道路上举办一场马拉松。为了让跑者经过城市中的许多地方,组织者设置了 个检查点。给定 的一个排列 ,检查点位于 ()。
组织者希望赛道易于遵循。因此,马拉松赛道必须满足以下全部条件:
- 赛道是一条只沿道路行进的闭合路线。仅在出发和结束时经过起点,其他任意点均不能经过超过一次。
- 赛道使用全部 条水平道路和全部 条竖直道路,且沿每条道路行进的距离至少为 。
- 赛道经过每个检查点,且在每个检查点都转弯。
- 赛道恰好转弯 次。
特别地,赛道不能自交,即使是在不转弯的道路交点处也不行。每次转弯时,赛道都会从水平道路转入竖直道路,或从竖直道路转入水平道路。
满足上述全部条件的路线称为合法路线。

图 I-1:合法与不合法的马拉松赛道示例。图中 Checkpoint 表示检查点,Valid 表示合法,Invalid 表示不合法。
图 I-1 展示了样例输入对应的合法与不合法路线。最左侧的路线满足全部条件,因此合法。第二条路线发生自交,因此不合法。第三条路线的转弯次数超过 ,因此不合法。最右侧的路线没有在每个检查点都转弯,因此不合法。
请输出一条满足全部条件的马拉松赛道。保证在给定约束下存在这样的赛道。
注意,你不需要最大化或最小化赛道的总长度。
输入格式
输入包含一组测试数据,格式如下。
N
P_1 P_2 ... P_N
第一行包含一个整数 (),表示每个方向上的道路数量。
第二行包含 个互不相同的整数 (),它们组成排列 。
输出格式
按照沿赛道经过的顺序,输出赛道转弯的 个道路交点,格式如下:
X_1 Y_1
X_2 Y_2
...
X_{2N} Y_{2N}
对于每个 (), 表示第 条水平道路与第 条竖直道路的交点,其中 。
如果存在多条合法路线,输出任意一条即可。
你可以选择任意一个转弯交点作为 ,并沿赛道的任意一个方向输出这些交点。
4
2 4 1 3
2 4
1 4
1 2
3 2
3 1
4 1
4 3
2 3