PROJECT EULER · #0644
数轴上的平方数
Squares on the Line
Sam 和 Tom 正在尝试玩一个游戏,通过轮流将单位方块放置到线段上来(部分)覆盖长度为
如下图所示,正方形可以通过两种不同的方式放置,要么是"直线",即在线段上放置两个相对边的中点,要么是"对角线",即在线段上放置两个相对的角。新放置的方块可以接触其他方块,但不允许与之前放置的任何其他方块重叠。
能够将最后一个单位方块放置在线段上的玩家获胜。
当山姆通过放置第一个方块来开始每场游戏时,他们很快意识到山姆每次都可以通过将第一个方块放置在线段的中间来轻松获胜,从而使游戏变得无聊。
因此,他们决定随机化山姆的第一步,首先抛掷一枚公平的硬币来确定正方形将在线段上直线还是对角线放置,然后随机选择在线段上的实际位置,所有可能的位置都具有相同的可能性。如果 Sam 输了比赛,他的比赛增益被定义为 0;如果他赢了,则比赛增益为
例如,如果
选择
由于对 Sam 的
您将获得
查找
题解待补充
这道题的题目已收录,解题思路、代码和答案将在后续补充。