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)