撰写时间限制(普通/Java) : 1000 MS/ 3000 MS 运行内存限制 : 65536 KByte
总提交 : 128 测试通过 : 2
比赛描述
当日遇到月，于是有了明。当我遇到了你，便成了侣。
那天，日月相会，我见到了你。而且，大地失去了光辉，你我是否成侣？这注定是个凄美的故事。
小张和所有世俗的人们一样，期待那百年难遇的日食。驻足街头看天，看日月渐渐走近，小张的脖子那个酸呀（他坚持这个姿势已经有半个多小时啦）。他低下仰起的头，环顾四周。忽然发现身边竟站着漂亮的赵mm。天渐渐暗下，赵mm在这街头竟然如此耀眼，她是天使吗？站着小张身边的天使。
小张对赵mm惊呼：“缘分呐~~”。赵mm却毫不含糊：“是啊，500年一遇哦！”（此后省略5000字….）
小张赶紧向赵mm要联系方式，可赵mm说：“我和你玩个游戏吧，赢了，我就把我的手机号告诉你。”小张，心想天下哪有题目能难倒我呢，便满口答应下来。赵mm开始说游戏规则：“这里有一个1*n的棋盘，我们轮流放一个棋子上去，并且用一样的棋子，你先放，谁最先将3个棋子连在一起谁就赢。”当然，出于对校长的考验，赵mm会尽力去赢得比赛。作为资深僚机的你，能帮助小张，得到赵mm的手机号吗？
输入
输入包括一行，这一行只包含一个整数n（3 ≤ n ≤ 2000）
输出
如果小张赢了则输出1，否则输出2
样例输入
6
样例输出
2
提示
input output
3 1
标程：
#include<cstdio>
#include<cstring>
const int maxn=2005;
int SG[maxn];
bool vis[maxn];
void sg()
{
memset(SG, 0, sizeof(SG));
SG[1] = 1; SG[2] = 1; SG[3] = 1;
for (int i = 4; i < maxn; i++)
{
memset (vis, 0, sizeof(vis));
for (int j = 2; j < i; j++)
{
if ((i-j-1 < 2)) vis[SG[j-2]^0] = true;
else vis[SG[j-2]^SG[i-j-1-2]] = true;
}
for (int j = 0; ; j++)
if (!vis[j]) {SG[i] = j ; break;}
}
}
int main ()
{
sg();
int n;
scanf("%d", &n);
if (SG[n]) puts("1"); else puts("2");
return 0;
}