Crosses and Crosses

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 file contains one integer number n (3 ≤ n ≤ 2000).

Output ‘1’ if the first player wins, or ‘2’ if the second player does.

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>//by NeighThornusing namespace std;const int maxn=2000+5;int n,f[maxn];inline int sg(int x){	if(f[x]!=-1)		return f[x];	bool vis[maxn];	memset(vis,0,sizeof(vis));	for(int i=1;i<=x;i++)		vis[sg(max(0,i-3))^sg(max(x-i-2,0))]=1;	for(int i=0;;i++)		if(!vis[i])			return f[x]=i;}signed main(void){	scanf("%d",&n);	memset(f,-1,sizeof(f));f[0]=0;	puts(sg(n)?"1":"2");	return 0;}