hiho一下第231周《小Ho的强迫症》题目分析

3
2

《小Ho的强迫症》题目分析

本题是一道数学题。

首先我们计算L和D的最大公约数G = gcd(L, D)。

假设起始时第一步脚跟与之前最近缝隙的距离是X,我们考虑每一步脚跟与之前最近的缝隙的距离。

那么显然一直走下去之后,X+G,X+2G,X+3G,... 即 {(X+KG) % L | K = 0, 1, ... } 这些位置并且仅有这些位置都一定会被踩到。

如果这些位置中有某个位置Y满足 Y + F > L,那么这一步就踩到了缝隙上。考虑到F和L都是定值,显然最大的Y越小越好。

于是有X=0时,位置集合是{0, G, 2G, 3G, ... L-G},最大值是L-G。

X=1时,位置集合是{1, 1+G, 1+2G, 1+3G, ... 1+L-G},最大值是L-G+1。

X=2时,位置集合是{2, 2+G, 2+2G, 2+3G, ... 2+L-G},最大值是L-G+2。

...

显然当X=0时,位置集合最大值L-G是最小的。

这时如果L - G + F > L即F > G时,脚会踩在缝隙上;否则就不会。

1 answer(s)

3

另一种分析思路:

...| F | G | F | G |...,其中G为D-F,则脚踩在缝隙上的条件为a*(F+G) < b*L < a*(F+G)+F
化简这个不等式等0 < b*L - a * D < F,即求是否存在整数a, b使得b*L - a*D的差最小且大于0。
b*L - a*D的大于0的最小差值其实就是等于gcd(L, D),所以gcd(L, D) < F就是脚踩在缝隙上的条件。

write answer 切换为英文 切换为中文


转发分享