0%

TOAD-puzzle-21

似乎我 YY 出一个不同的方法?

problem

无穷平面上有两个点 \(A, B\) ,两点距离为 \(D\)\(A\) 一步可以移动到距离不超过 1 的地方。而且 \(A\) 移动后可以知道距离 \(B\) 是远了还是近了。求一种方法使得 \(A\) 移动 \(D + o(D)\) 步后两点距离不超过 1 。\(f(x) = o(g(x))\) 表示 \[\lim_{x \to \infty} \frac{f(x)}{g(x)} = 0\]

solution

假设我们找到一条过 \(A\) 的直线,使得 \(B\) 到这条直线的距离不超过 \(\frac{1}{2}\) ,那么这个问题就很容易了,我们沿着这条直线走即可,最后几步微调一下。

给定一条直线,如何判断 \(B\) 到这条直线的距离不超过 \(\frac{1}{2}\) 呢?我们沿与直线垂直的方向跳,左右各跳一次,如果两次都是距离变远了,那么距离就不超过,否则一定超过 \(\frac{1}{2}\)

所以现在的任务是找到一条直线。我们建立一个直角坐标系,先检验两条坐标轴是否满足要求,如果不满足,那么我们可以找到 \(B\) 在哪个象限。

考虑如图所示区域(不会 tikz 只好用 GeoGebra 了),假设我们已经把 \(B\) 点的范围确定在 \(\alpha\) 内,这次我们判断角 \(\alpha\) 的平分线 \(AD\) 是否可行。如果 \(AD\) 不行,我们就可以将角度减小为原来的一半。

时间复杂度?我觉得是 \(O(\log D)\) 的。注意 \(\frac{AD}{AE} = \frac{1}{2 \cos \frac{1}{4}\alpha} = \frac{\sin \frac{1}{4}\alpha}{\sin \frac{1}{2} \alpha}\) 。当 \(\alpha \to 0\) 时, \(\frac{AD}{AE} = \frac{1}{2}\) 也就是 \(AE = 2AD\) ,所以只需要 \(O(\log D)\) 次即可找到要求直线,而 \(O(\log n) = o(D)\)

nonsense

本来这篇文章在去北京旅游之前就写完了的,但是由于 jekyll 突然之间挂了我就不好说啥了。

回学校 pacman -Syu 后发现 libpng 挂了,幸亏 QQ 还可以上然后借助文学巨匠 @wzy 的力量终于修好了。然后再试试 jekyll 发现居然好了真是太令人开心了。

所以说一个生活用的 Linux 就是一个配置好了后不 Syu 的 Arch Linux 么 233 不过我用 Linux 的一个很重要的原因就是 学zhuang习bi 吧。wzy 说把 Windows 玩坏了他不知道该怎么办,其实我把 Linux 玩坏了不也是玩不会来了 233

由于到北京的第一天笔记本就来了(这神奇的速度),于是这几天天天在玩 Windows 8 水人人水 GM 水贴吧水各种各样的网站。一开始的时候还是有点不习惯,现在感觉差不多还行吧。不过一堆设置没有真是蛋疼。(为啥我感觉现在我用的输入法都这么准呢?一定是我的错觉)

所以说一直拖着拖到现在才发这篇文章真是对不起了(又没人看说啥对不起呢 —— 不要在意这些细节)

今天下了个 SSD 的订单,明天应该就可以来,我还不会装呢,到时候请老师帮忙吧。光驱是 SATA2 真是对不起啊,不过 SSD 要是能达到 SATA2 的上界我也不得不服。