久等了,造句一直不是我的强项。
先看看这个问题的AC代码。
程序代码:
#include<stdio.h>
int main()
{
int n;
while(scanf("%d%d", &n, &n), n)//不要怀疑这句,就是这样。看不懂说明你的基础还很差,继续努力吧
puts(n <= 4 ? "Yes" : "No");
return 0;
}
是不是极度简单?但简单的只是它的外表。
这只是冰山浮出水面的一角。我们来看看支撑这简单一角下面的理论基础是什么吧。
Tom 和 Jerry 足够聪明。这句话不起眼,但却是一个很关键条件。
这意味着双方完全明白自己和对方能采取哪些策略,以及自己采取某一策略后对方会如何应对。所以不要耍小聪明。
这是博弈论的一个重要题设。
对于Tom来说,它的目的是抓住Jerry。为实现这一目的它的策略就是随时保持与Jerry的距离最短。
对于Jerry来说,它的目的是逃离池塘不被Tom抓到。为实现这一目的它的策略是尽量靠近池塘边缘并尽量与Tom保持足够远的距离。
这一问题的结构决定了在极坐标系下分析它更合适。
设Jerry在池塘中的位置到中心的距离为r,则它与池塘边缘的最大距离为r + R(R为池塘半径)。这也是Jerry在池塘该位置里能与Tom保持的最大距离。
由于Tom和Jerry的线速度是有上限的,并且不等。所以Jerry不可能在池中任何位置都与Tom保持在最大位置,越靠近池边Jerry运动的角速度越小,Tom将有机会绕到近处。
那么Jerry能保持的这个最大距离中的r到底可以有多大呢?Jerry的最大速度为1,这个速度可以分解为两个速度的矢量和,一个平行于极径指向外,一个垂直于极径。
平行于极径的速度分量使得Jerry靠近池塘边,垂直于极径的速度分量用于与Tom周旋。
两个速度的和是一个定值,所以当Jerry的速度全部用于与Tom周旋时将达到r的最大值。
此时Tom和Jerry的角速度相同,即
N / R == 1 / r
==> r = R / N
这时,Jerry距离池塘边还差R - r == R * (1 - 1 / N)
Jerry要做的就是在Tom到来前先上岸,它该以什么方式上岸呢?
直接沿最短距离R - r游上岸,这样它用的时间最短(在数量上所用时间也等于R - r)。但同样这时Tom跑到它面前所需要的时间也是最短的。
沿一条螺线游上岸,Tom会不会需要的时间更长一些?会。但同样Jerry上岸需要的时间也更长。具体该怎么做,需要分析一下了。
设Jerry以与极径保持u的夹角向岸边极力游去。
这时,Jerry游到岸边需要的时间为Tj = (R - r) / cos(u)
Jerry游过的角度是一个定积分式
w = S(sin(u) * dt / ( r + cos(u) * dt))[0 -> Tj]
==> w = ln(R - r) * tan(u)
这时Tom追到Jerry上岸的地点所需时间为Tt = (ln(R - r) * tan(u) + PI) * R / N
我们希望Tt 尽量大于 Tj, 即
sin(u) * ln(R - r) + PI * cos(u) > R * (R - r) / N
由于r = R / N,上式右边是常数,那么就代入左边
sin(u) * ln(N / (N - 1)) + PI * cos(u)
由于N为整数,当N > 1时,ln(N / (N - 1)) < PI,所以上式取最大值时u为0。
所以Jerry沿直线游向岸边是最佳策略。
由此,Jerry想成功逃跑的条件就是
R - r < PI * R / N
==> R * (1 - 1 / N) < PI * R / N
==> N < PI + 1
由这个推导过程可以看出,决定Jerry能否逃跑的因素与池塘的大小无关,只与Tom的速度有关。
由于N的取值为整数,所以在我的代码中上面条件简化成了 N <= 4。