[中譯] ProjectEuler 391 Hopping Game

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者babufong (嗶嗶)時間13年前 (2012/07/01 12:15)推噓1(1推 0噓 0→)

留言1則, 1人參與討論串1/1

391. Hopping Game http://projecteuler.net/problem=391 使 s_k 為將 0 到 k 的數字以二進制表示時 1 的數量。舉例來說，將 0 到 5 以二進制表示時，我們得到 0, 1, 10, 11, 100, 101 一共有 7 個 1，故 s_5 = 7。而數列 S = { s_k : k≧0 }，起始幾項為 {0, 1, 2, 4, 5, 7, 9, 12, ...} 有個遊戲是兩人玩的，遊戲開始前會先選擇一個數字 n，且有個計數器 c 起始值為 0。輪到某玩家的回合時，該玩家選擇 1 到 n（含）的其中一個數字且將該數加至計數器上而 c 的值一定要是 S 的其中一位成員。如果怎麼選擇並加至計數器中皆無法達成條件，該玩家輸掉這遊戲。這有個例子：起初選擇 n = 5，c = 0。玩家 1 選擇 4，所以 c 為 0 + 4 = 4。玩家 2 選擇 5，所以 c 為 4 + 5 = 9。玩家 1 選擇 3，所以 c 為 9 + 3 = 12。以此類推記得，c 一定屬於 S，且每位玩家都可以將至多 n 的數加到 c 上。使 M(n) 為玩家 1 在第一回合中，為了使自己一定會獲得勝利，所能選擇最大的數。如果怎麼選都做不到，則 M(n) = 0。舉例，M(2) = 2、M(7) = 1、M(20) = 4。已知 Σ(M(n))^3 = 8150，當 1 ≦ n ≦ 20。請求出 Σ(M(n))^3，當 1 ≦ n ≦ 1000。 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 125.224.2.175