[中譯] ProjectEuler 426 Box-ball system
426. Box-ball system
http://projecteuler.net/problem=426
有一排無限多的箱子，並在其中一部分的箱子裡放了一顆球。
舉例來說，如果我們由左至右有兩個箱子有球、兩個空箱、兩個箱子有球、一個空箱、
兩個箱子有球，其餘均為空箱，則我們記作(2, 2, 2, 1, 2)，依序代表有球和沒球的
箱子個數。
定義一回合的行動為依序對每顆球進行一次如下動作：把最左邊沒動過的球移到其右邊
最接近的空箱。
在經過一回合的行動後，(2, 2, 2, 1, 2)會變成(2, 2, 1, 2, 3)，如下圖所示；注意
到所有的狀態表示永遠都是從第一個有球的箱子開始計算。
http://projecteuler.net/project/images/p_426_baxball1.gif
上述系統一般稱之為箱球系統（Box-Ball System），或簡寫為BBS。
可以證明在經過足夠多回合的行動後，此系統會演變成一穩定狀態，使得每個接連有球
的箱子數不會再改變。在下面這個例子中，接連有球的的箱子數最終演變為[1, 2, 3]；
我們把這種狀態稱為其終態。
http://projecteuler.net/project/images/p_426_baxball2.gif
我們定義一數列{t_i}如下：
‧s_0 = 290797
‧s_(k+1) = s_k^2 mod 50515093
‧t_k = (s_k mod 64) + 1
如果由初始狀態(t_0, t_1, ..., t_10)開始行動，則其終態為[1, 3, 10, 24, 51, 75]。
試求由初始狀態(t_0, t_1, ..., t_10000000)開始行動的終態。
請給出每個終態元素的平方和作為最終答案。例如如果終態是[1, 2, 3]，則答案為
1^2 + 2^2 + 3^2 = 14。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 129.2.129.163
※ 編輯: tml 來自: 129.2.129.163 (05/05 15:56)
puzzle 近期熱門文章
5
21
PTT遊戲區 即時熱門文章
22
24
