ACM通信

最后一个字节

Upstart puzzle: Ice Trap

丹尼斯·沙沙村
ACM通信，2016年1月，第59卷第1期，第136页
10.1145 / 2851212
评论

想象一个500平方乘500平方的红黑相间的冰棋盘，四边都是墙。无摩擦冰球在棋盘的对角线上方移动，方向为西北、东北、东南或西南(你不知道冰球从哪个方向或从哪里开始)，速度为每个时间单位的一个对角线平方。你要把它困在一个一平方乘一平方的地方。

你可以在棋盘上设置任意长度的水平(东西方向)或垂直(南北方向)墙，但你的总墙长度是有限的T。为了建造你的第一面墙l你至少要等天花板。l/10)游戏开始的时间单位。建造:建造任何长度的后续墙l’，你至少要等天花板。L '10)从你建造最后一堵墙开始算起的时间单位。一旦你被允许筑起一堵墙，它就会立刻出现。你也可以随时拆毁你所筑的城墙。如果当你试图筑起一堵墙时，冰球正好在墙覆盖的方格内，那么这堵墙就不会被筑起(你会被告知这堵墙会击中冰球)。之后你可以建一堵新墙l/10个时间单位。

如果冰球击中了一堵墙或一堵固定的墙，它会反弹到反射的对角线上;例如，如果冰球向东南移动，击中了你的南北方向的墙，它就会从它击中墙的地方向南的一个方格向西南方向反弹，同时也会改变棋盘上的颜色方格从黑色变为红色或红色变为黑色。

我们考虑三种检测场景:

哪面墙，哪边，哪里，撞。如果冰球击中了你竖起的任何一堵墙，你就知道哪堵墙被击中了，在哪边，在哪里。但当冰球撞到固定侧壁时，你就不会知道了。

这墙。如果冰球击中了你的任何一堵墙，你知道哪堵墙被击中了，但不知道冰球击中了哪里。

知道有墙被撞了。如果冰球击中了你的任何一堵墙，你只知道有一堵墙被击中了，但不知道是哪一堵墙。

对于每一种情况，你的目标是在尽可能短的时间内(最坏的情况下)将冰球限制在一个正方形接一个正方形的区域内，无论冰球从哪里开始或最初朝哪个方向移动。

在最困难的情况下(第二种情况)，如果壁长只有502个方格，你如何保证将冰球限制在一个1乘1的方格内?

解决方案。下面的解决方案草图由纽约大学新生丹·西蒙完成。让我们将西南方格固定为(0,0)，其中第一个坐标表示南北方向。等待50个时间单位后，从(0,1)到(499,1)建立一个南北墙。冰球最终会击中那堵墙。如果它很快再次击中，那么你就把冰球困在(0,0)和(499,0)之间的狭窄巷子里。否则冰球将向东移动，所以在50个单位后，你可以拆除这堵墙，并在(0,53)到(499,53)之间建立另一堵墙。那堵墙会把冰球反射回来。然后你可以拆除这堵墙，52个时间单位后，你可以在(0,1)到(499,1)处建造一堵新墙。

现在你已经把冰球困在一个单位厚度的巷道里了。现在在(250,0)处设置一个位垒。冰球最多能在500个时间单位内击中它。现在在(252,0)处设置障碍。如果冰球击中了它，你就把冰球困住了。否则，在(246,0)和(248,0)处设置障碍。

Upstart 1。如果你能以某种方式把冰球逼到有固定墙壁的角落里，那么可以想象的最小墙的长度是三个棋盘格。你真的能用那种方法把冰球困住吗?如果不是，你需要捕捉冰球的最小长度是多少，如何捕捉?

Upstart 2。为最小壁长在所有三种检测场景中找到最优最差情况保证。

回到顶部

回到顶部

数字图书馆是由计算机协会出版的。版权所有©2016 ACM, Inc.

---

没有发现记录