← 完整题目索引

PROJECT EULER · #0334

洒落豆子

Spilling the Beans

仅题目 · 待解原题 ↗

在柏拉图的天堂里,在一条直线上存在无数个碗。
每个碗要么包含一些有限数量的豆子,要么不包含有限数量的豆子。
一个孩子玩一个游戏,该游戏只允许一种移动:从任何碗中取出两颗豆子,然后在两个相邻的碗中各放入一颗豆子。
当每个碗包含一颗豆子或没有豆子时,游戏结束。

例如,考虑两个相邻的碗分别包含 2 和 3 豆,所有其他碗都是空的。以下八步将完成游戏:

0334_beans.gif

您将获得以下序列:

t0=123456,ti={ti−12,if ti−1 is even⌊ti−12⌋⊕926252,if ti−1 is oddwhere ⌊x⌋ is the floor function and ⊕is the bitwise XOR operator.bi=(timod211)+1.

式中的 even、odd 分别表示偶数、奇数;floor function 表示下取整函数,bitwise XOR 表示按位异或运算。

最后一个序列的前两项是 b1=289 和 b2=145。
如果我们从两个相邻碗中的 b1 和 b2 豆子开始,则需要 3419100 移动才能完成游戏。

现在考虑 1500 相邻的碗,分别包含 b1,b2,…,b1500 豆子,所有其他碗都是空的。找出游戏结束前需要移动多少步。

题解待补充

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