在一個稱為『六芒星』的星球上,流行著一種『六芒星棋』的遊戲。這種遊戲是由兩個人來比賽,道具是一個棋盤(如圖一)和13 個鐵圈。遊戲的起始狀態是由兩人互相協調或隨機決定,使用m 個(1 ≤ m ≤ 13)鐵圈在棋盤上圈住m 個數字。接下來雙方輪流移除棋盤上的鐵圈,每人每次只能移除1 個鐵圈或2個相鄰的鐵圈(有直線直接相連的位置視為相鄰),被迫移除最後一個鐵圈的人算輸。
其實如果仔細思考,可以證明不管起始狀態如何,遊戲中先移除鐵圈的人(先手)與其對手(後手)中必定恰有一人,只要他每次都用對自己最有利的方法來移除鐵圈,最後一定百分之百得勝。
以起始狀態如圖二為例,因為所有鐵圈均不相鄰,故一次只能移除一個鐵圈,先手不管移除哪一個圈,後手只要再移除一個圈,就可以逼迫先手移除最後一個圈,因此後手有百分之百得勝的把握,我們說成『圖二的起始狀態是後手有利』。若起始狀態如圖三就不同了,如果先手懂得先移除相鄰的兩個鐵圈(如27 與210),就可以迫使後手去移除最後一個圈,因此先手就有百分之百得勝的把握,我們說成『圖三的起始狀態是先手有利』。每一種起始狀態,我們用一個整數來表示它,這個整數就是在該起始狀態中所有被鐵圈圈住的數字總和。例如圖二的起始狀態可以用27+25+211=2088 表示,圖三則可用27+29+210=1664 來表示。
請你寫一個程式來判斷在不同的起始狀態下,到底是先手還是後手有利。
輸入說明:
第一行為一個整數n,1 ≤ n ≤ 10,代表接下來的n 行中每一行有一個以整數
表示的起始狀態。
對每一個輸入的起始狀態,程式必需依順序輸出它們是先手有利(以1 表
示)還是後手有利(以0 表示)。也就是說,輸出為n 個0 或1 的數字,數字間
請用一個空白字元隔開。
2016.12.13 範測修正 by Paupière
原TIOJ1150 / 94全國賽(prob 5)。
No. | Testdata Range | Score |
---|---|---|
1 | 0 | 25 |
2 | 1 | 25 |
3 | 2 | 25 |
4 | 3 | 25 |