Crosses and Crosses
Time Limit: 3000MS | Memory Limit: 65536K | |
Total Submissions: 3063 | Accepted: 1196 | |
Case Time Limit: 2000MS |
Description
The game of Crosses and Crosses is played on the field of 1 × n cells. Two players make moves in turn. Each move the player selects any free cell on the field and puts a cross ‘×’ to it. If after the player’s move there are three crosses in a row, he wins.
You are given n. Find out who wins if both players play optimally.
Input
Input file contains one integer number n (3 ≤ n ≤ 2000).
Output
Output ‘1’ if the first player wins, or ‘2’ if the second player does.
Sample Input
#1 | 3 |
---|---|
#2 | 6 |
Sample Output
#1 | 1 |
---|---|
#2 | 2 |
Source
Northeastern Europe 2007, Northern Subregion
【思路】
SG函数,博弈
题目treblecross的简化。
【代码】
#include<cstdio>
#include<cstring>
using namespace std; const int N = +; int sg[N],n; int dfs(int x) {
if(x<=) return ;
if(sg[x]!=-) return sg[x];
int vis[N];
memset(vis,,sizeof(vis));
for(int i=;i<=x;i++)
vis[dfs(i-)^dfs(x-i-)]=;
for(int i=;;i++)
if(!vis[i]) return sg[x]=i;
} int main() {
memset(sg,-,sizeof(sg));
while(scanf("%d",&n)==) {
if(dfs(n)) puts("");
else puts("");
}
return ;
}