ARC103B Robot Arms

发表于 更新于 分类于 ， ， 阅读次数：

题意：给定 个坐标 。

构造长度为 的序列 ，满足：

  • 表示第 步「步长」。
  • 对于每个坐标，从 开始走，共走 步。第 步可以让 变成 或 。
  • 走完 次之后，恰好走到这组坐标。
  • 要求 ， 。

给出 的具体值，以及每个坐标的行动方向序列。或指出无解。

，，时限 。

不难发现，最终到达的点的 的奇偶性是相同的。故若给定的坐标中 的奇偶性有不同，则无解。

观察下列图像，图中 i 是走第 步能到达的范围：

1
2
3
4
5
6
7
.......
.......
...1...
..101..
...1...
.......
.......

。

1
2
3
4
5
6
7
...2...
..212..
.2.2.2.
2120212
.2.2.2.
..212..
...2...

。

不难发现，只需令 ，就能达到 以内的任何 为奇数的位置。

若要到所有 为偶数的位置，则在 后面再加一个 即可。

最后考虑如何构造方向方案。

对于四种方向，走向离目的地曼哈顿距离最小的一个。不难理解正确性。