b066. 5. 六芒星棋遊戲：先還是後比較有利？
b066. 5. 六芒星棋遊戲：先還是後比較有利？
內容 ：
在一個稱為『六芒星』的星球上，流行著一種 『六芒星棋』的遊戲。這種遊戲是由兩個人來比賽，道具是一個棋盤（如圖一）和13 個鐵圈。遊戲的起始狀態是由兩人互相協調或隨機決定，使用m 個（1 ≤ m ≤ 13）鐵圈在棋盤上圈住 m 個數字。接下來雙方輪流移除棋盤上的鐵圈，每人每次只能移除1 個鐵圈或 2 個相鄰的鐵圈（有直線直接相連的位置視為相鄰），被迫移除最後一個鐵圈的人算輸。
其
實如果仔細思考，可以證明不管起始狀態如何，遊戲中先移除鐵圈的人（先手）與其對手（後手）中必定恰有一人，只要他每次都用對自己最有利的方法來移除鐵
圈，最後一定百分之百得勝。以起始狀態如圖二為例，因為所有鐵圈均不相鄰，故一次只能移除一個鐵圈，先手不管移除哪一個圈，後手只要再移除一個圈，就可以
逼迫先手移除最後一個圈，因此後手有百分之百得勝的把握，我們說成『圖二的起始狀態是後手有利』。若起始狀態如圖三就不同了，如果先手懂得先移除相鄰的兩
個鐵圈（如27 與210），就可以迫使後手去移除最後一個圈，因此先手就有百分之百得勝的把握，我們說成『圖三的起始狀態是先手有利』。
每一種起始狀態，我們用一個整數來表示它，這個整數就是在該起始狀態中所有被鐵圈圈住的數字總和。例如圖二的起始狀態可以用23+25+211=2088 表示，圖三則可用27+29+210=1664 來表示。
請你寫一個程式來判斷在不同的起始狀態下，到底是先手還是後手有利。
輸入說明
：
第一行為一個整數n，1 ≤ n ≤ 10，代表接下來的 n 行中每一行有一個以整數表示的起始狀態。
輸出說明
：
對每一個輸入的起始狀態，程式必需依順序輸出它們是先手有利（以 1 表示）還是後手有利（以 0 表示）。也就是說，輸出為 n 個 0 或 1 的數字，數字間請用一個空白字元隔開。
範例輸入 ：
3 32 1024 1664 5 6 13 19 2088 2305
範例輸出 ：
0 0 1 1 1 0 0 0
提示
：
出處
：
作法 : DP
從最終盤面, 慢慢推回到原始盤面, 原本輸的盤面, 推回去會變成贏的盤面,
然而先手有利, 只限定在百分之百獲勝, 也就是說, 有一個會輸, 就是先手不利,
因此用一個 or 去做運算
/**********************************************************************************/
/* Problem: b066 "5. 六芒星棋遊戲：先還是後比較有利？" from 94全國資訊學科能力決賽*/
/* Language: C */
/* Result: AC (6ms, 250KB) on ZeroJudge */
/* Author: morris1028 at 2011-08-22 12:03:57 */
/**********************************************************************************/
#include<stdio.h>
int DP[8192] = {};/*0 win, 1 unsure*/
int LK[13][7] = {
{2,3,-1},
{2,5,-1},
{0,1,3,5,6,-1},
{0,2,4,6,7,-1},
{3,7,-1},
{1,2,6,8,9,-1},
{2,3,5,7,9,10,-1},
{3,4,6,10,11,-1},
{5,9,-1},
{5,6,8,10,12,-1},
{6,7,9,11,12,-1},
{7,10,-1},
{9,10,-1}
};
void Build() {
int a, b, c, tn, t;
for(a = 1; a <= 8191; a++) {
tn = a;
for(b = 0; b < 13; b++) {
t = tn&(1<<b);
if(t == 0) {
t = tn|(1<<b);
DP[t] |= !DP[tn];
}
}
for(b = 0; b < 13; b++)
for(c = 0; LK[b][c] >= 0;c++) {
t = tn&((1<<b)|(1<<LK[b][c]));
if(t == 0) {
t = tn|(1<<b)|(1<<LK[b][c]);
DP[t] |= !DP[tn];
}
}
}
}
main() {
Build();
int n, x, a;
while(scanf("%d", &n) == 1) {
while(n--)
scanf("%d", &x), printf("%d ", DP[x]);
puts("");
}
return 0;
}