Crosses and Crosses
Time Limit: 3000MS Memory Limit: 65536K
Total Submissions: 4049 Accepted: 1586
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

6

Sample Output
2

Source

Northeastern Europe 2007, Northern Subregion
 
 
/*
因为只要有三个X连起来就赢了,所以肯定不能在X旁边或者旁边的旁边放,不然下一步对手就赢了。
所以放X就相当于把序列分割成 1/2 块。
sg(x)表示长度为x且两端 不能放的SG函数
*/
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define ll long long
#define maxn 2005
using namespace std;
int sg[maxn],n,m;
int v[maxn*];
inline void init(){
sg[]=sg[]=sg[]=;
sg[]=sg[]=sg[]=; int now,x,y;
for(int i=;i<=;i++){
v[sg[i-]]=i;
x=,y=i-;
while(x<=y){
v[sg[x]^sg[y]]=i;
x++,y--;
} now=;
while(v[now]==i) now++;
sg[i]=now;
}
} int main(){
init();
// for(int i=1;i<=20;i++) printf("%d %d\n",i,sg[i]);
while(scanf("%d",&n)==){
if(sg[n+]) puts("");
else puts("");
}
return ;
}
05-10 22:57
查看更多