← 完整题目索引

PROJECT EULER · #0644

数轴上的平方数

Squares on the Line

仅题目 · 待解原题 ↗

Sam 和 Tom 正在尝试玩一个游戏,通过轮流将单位方块放置到线段上来(部分)覆盖长度为 L 的给定线段。

如下图所示,正方形可以通过两种不同的方式放置,要么是"直线",即在线段上放置两个相对边的中点,要么是"对角线",即在线段上放置两个相对的角。新放置的方块可以接触其他方块,但不允许与之前放置的任何其他方块重叠。
能够将最后一个单位方块放置在线段上的玩家获胜。

0644_squareline.png

当山姆通过放置第一个方块来开始每场游戏时,他们很快意识到山姆每次都可以通过将第一个方块放置在线段的中间来轻松获胜,从而使游戏变得无聊。

因此,他们决定随机化山姆的第一步,首先抛掷一枚公平的硬币来确定正方形将在线段上直线还是对角线放置,然后随机选择在线段上的实际位置,所有可能的位置都具有相同的可能性。如果 Sam 输了比赛,他的比赛增益被定义为 0;如果他赢了,则比赛增益为 L。假设 Sam 初始移动后两名玩家都处于最佳状态,您可以看到 Sam 的预期增益(称为 e(L))仅取决于线段的长度。

例如,如果 L=2,Sam 将以 1 的概率获胜,因此 e(2)=2
选择L=4,中奖概率为直线情况为0.33333333,对角情况为0.22654092,导致e(4)=1.11974851(四舍五入至8小数点后位数)。

由于对 Sam 的 L 的最佳值感兴趣,我们将 f(a,b) 定义为某些 L[a,b]e(L) 的最大值。
您将获得 f(2,10)=2.61969775L=7.82842712f(10,20)=5.99374121(四舍五入为 8 位)。

查找 f(200,500),四舍五入为 8 小数点后的数字。

题解待补充

这道题的题目已收录,解题思路、代码和答案将在后续补充。