回分類題庫
e003: 3.新井字遊戲
關鍵字: 100學年度全國決賽

測資點 : 7 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 27 Times / 23 Users | Submit : 71 Times / 26 Users | Accepted rate : 88%
題目加入時間 : 2015-11-12 09:40

Content: 简体中文

在台灣宜蘭的一個小鄉鎮裡,小學生之間流傳著一個稱為『新井字』的雙人對弈遊戲。這種遊戲使用的道具是一個『井』字形的棋盤(如圖一所示),和 12 個棋子。遊戲開始時,棋盤上每一個標示英文字母的地方,都可以隨機決定要不要擺放一個棋子(但是當然不能整個棋盤都不放棋子)。遊戲進行的規則是由兩個遊戲者輪流取走棋盤上的棋子,每人每次必須取走棋盤上任意 1 個或 2 個相鄰(棋盤上有直線相連)的棋子,而被迫取走最後一個棋子的人算輸,另一位遊戲者則得勝。

 

其實如果仔細思考,可以證明不管遊戲開始時的棋盤狀態(簡稱起始狀態)如何,先開始取棋子的人(先手)與其對手(後手)二人中必定恰有一人,只要他每次都用對自己最有利的方法,最後一定會得勝。舉例來說,若起始狀態中只有A、B、F 處有棋子,則先手不管取走哪一個棋子,後手只要再移除一個棋子,就可以逼迫先手去取最後一個棋子,因此後手有百分之百得勝的把握,我們可以說『這個起始狀態是後手有利』。再舉另一個例子,若起始狀態只有 A、C、D 處有棋子,則先手只要懂得先取走 A 與 D 處相鄰的兩個棋子,就可以迫使後手去取最後一個棋子,因此先手就有百分之百得勝的把握,我們可以說『這個起始狀態是先手有利』。本題就是要請你寫一個程式,來判斷在不同的起始狀態下到底是先手還是後手有利。 

Input:

第一行只含一個整數 n (1<=n<=10),告訴你總共有多少個起始狀態需要判斷。接下來的 n 行,每一行表示一種起始狀態。起始狀態是以連續 12 個 1 或 0 的數字來依序表示 A 到 L 的位置上有沒有棋子,1 代表該位置有棋子,0 表示該位置沒有棋子。

Output:

對於輸入的每一種起始狀態,若該起始狀態為對先手有利,你的程式必須輸出一個字元 1,若對後手有利,則必須輸出一個字元 0。因為輸入總共有 n 個起始狀態,因此總共必須輸出 n 個字元在同一行,且這些字元之間不需留空白。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
輸入1:
1
110001000000

輸入2:
2
101100000000
001100110010

Sample Output :

輸出1:
0

輸出2:
11

Hint :

Author :

100學年度全國決賽 (管理員:sagit)

  Solve it!   Status Forum