[中譯] ProjectEuler 459 Flipping game

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者tml (流刑人形)時間12年前 (2014/02/25 07:49)推噓0(0推 0噓 0→)

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

459. Flipping game http://projecteuler.net/problem=459 翻棋遊戲是一種兩個人玩的遊戲，需要一塊N乘N的棋盤。每個格子上都有一面黑一面白的黑白棋一枚。開始時每一枚棋子都是白色朝上。一個回合代表將一個符合條件的長方形內的所有棋子都翻轉一次，其條件為： ‧長方形的右上角必須是白棋 ‧長方形的寬必須是完全平方數n^2 (1, 4, 9, 16, ...) ‧長方形的長必須是三角形數n(n+1)/2 (1, 3, 6, 10, ...) 　●○○●○　●○○●○　●○○●○ 　○○○●●　○○○●●　○●●○○ 　●○●●○→●○●●○→●●○○● 　○○●○○　○○●○○　○●○●● 　○●●●○　○●●●○　○●●●○ 兩個玩家交互輪流，最先把所有白棋翻成黑棋的玩家獲勝。令W(N)為使用N乘N棋盤時，先手玩家必勝的第一手方法數、並假設雙方均使用最佳策略。則W(1) = 1、W(2) = 0、W(5) = 8以及W(10^2) = 31395。在N = 5時，先手玩家必勝的第一手列示如下　●●●○●　●●●●●　●●●●●　●●●●● 　●●●●●　●●●○●　●●●●●　●●●●● 　●●●●●　●●●●●　●●●○●　●●●●● 　●●●●●　●●●●●　●●●●●　●●●○● 　●●●●●　●●●●●　●●●●●　●●●●●　　●●●●●　●●●○●　●●●●●　●●●●● 　●●●●●　●●●○●　●●●○●　●●●●● 　●●●●●　●●●○●　●●●○●　●●●○● 　●●●●●　●●●●●　●●●○●　●●●○● 　●●●○●　●●●●●　●●●●●　●●●○● 請求出W(10^6)。 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 129.2.129.154