This is an interactive task (where your program interacts with the judge's program via Standard Input and Output). You are given integers $N$, $L$, and $R$. There are $N$ cards numbered $1$ through $N$ on the table. The first player to become unable to perform the operation loses, and the other player wins. Choose whether to go first or second, and play the game against the judge to win. This is an interactive task (where your program interacts with the judge's program via Standard Input and Output). Initially, receive $N$, $L$, and $R$, given from the input in the following format: First, you choose whether to go first or second. Print Then, the game immediately starts. If you choose to go first, the judge goes second, and vice versa. You are to interact with the judge via input and output until the game ends to win the game. In your turn, print an integer pair $(x, y)$ that you choose in the operation in the following format. If there is no $(x, y)$ that you can choose, print $(x, y) = (0, 0)$ instead. In the judge's turn, the judge print an integer pair $(a, b)$ in the following format: Here, it is guaranteed that $(a, b)$ is of one of the following three kinds. If the judge returns $(a,b)=(0,0)$ or $(a,b)=(-1,-1)$, the game has already ended. In that case, terminate the program immediately. The following is a sample interaction where $N = 6, L = 1$, and $R = 2$.Problem Statement
You play the following game against the judge:
The players alternately perform the following operation:
Constraints
Input and Output
$N$ $L$ $R$
First if you choose to go first, and Second if you choose to go second.$x$ $y$
$a$ $b$
Notes
Sample Interaction
Input
Output
Description
6 1 2
Initially, you are given integers $N$, $L$, and $R$.
FirstYou choose to go first and start the game.
2 1$(x, y) = (2, 1)$ is chosen to remove card $2$.
3 2
$(x, y) = (3, 2)$ is chosen to remove cards $3, 4$.
6 1$(x, y) = (6, 1)$ is chosen to remove card $6$.
5 1
$(x, y) = (5, 1)$ is chosen to remove card $5$.
1 1$(x, y) = (1, 1)$ is chosen to remove card $1$.
0 0
The judge is unable to perform the operation, so you win.
首先先玩着试一下。假设 \(N=11,L=R=3\) 吧。\(0\) 表示未取，\(1\) 表示已取。
0 0 0 0 0 0 0 0 0 0 0
突然发现，如果我们第一步去了中间的部分，那么情况就会变成
0 0 0 0 1 1 1 0 0 0 0
然后此时左右情况对称，对手怎么取，我在另一个方向同样方式取。这样的话对手怎么做，我都有方法做出反映。此时先手必胜。
但是这种方法不能用在所有情况。比如 \(N=11,L=R=2\) 时就不能构造出两个对称的位置。但是这样可以解决所有 \(L\ne R\) 的情况。
我们现在只用研究 \(L=R\) 的情况了。这个时候可以用 SG 函数解决。
根据 SG 函数的定义，设 \(f_i\) 为有 \(i\) 个数时的 SG 函数，那么 \(f_i=\operatorname{mex}\limits_{j\le i-l}\{f_j\oplus f_{i-l-j}\}\)。如果 \(f_n\) 等于0，后手必胜。否则先手必胜。
若 \(f_n\ne 0\)，可以先枚举每种方案，找到一种合法方案使得取完后 SG 函数为 0。而后面对手做出操作时，也一样找到一种方案使得 SG 函数为 \(0\)。这样一直维护，对手怎么操作我都有后续操作。所以肯定必胜。
SG 函数可以每次重算，不用想烦人的维护。反正瓶颈不在这。
#include<bits/stdc++.h>
const int N=2005;
int n,l,r,md,k,x,y,f[N],t[N],s[N],nxt[N],lst[N];
int main()
{
scanf("%d%d%d",&n,&l,&r);
if(l!=r)
{
if(n-l&1)
k=l+1;
else
k=l;
md=n+k>>1;
puts("First");
printf("%d %d\n",md-k+1,k);
fflush(stdout);
while(1)
{
scanf("%d%d",&x,&y);
if(!x)
break;
if(x<md)
printf("%d %d\n",x+md,y);
else
printf("%d %d\n",x-md,y);
fflush(stdout);
}
}
else
{
for(int i=l;i<=n;i++)
{
memset(s,0,sizeof(s));
for(int j=0;j<=i-l;j++)
s[f[j]^f[i-l-j]]=1;
for(int j=0;j>=0;j++)
if(!s[j])
f[i]=j,j=-5;
}
if(f[n])
{
puts("First");
for(int i=0;i<=n;i++)
{
if(!(f[i]^f[n-l-i]))
{
printf("%d %d\n",i+1,l);
for(int j=i+1;j<=i+l;j++)
t[j]=1;
i=n+1;
}
}
}
else
puts("Second");
t[n+1]=t[0]=1;
fflush(stdout);
while(1)
{
scanf("%d%d",&x,&y);
if(!x&&!y)
break;
k=0;
for(int i=x;i<=x+y-1;i++)
t[i]=1;
for(int i=n;i>=0;i--)
{
nxt[i]=nxt[i+1];
if(t[i+1])
nxt[i]=i+1;
if(t[i])
k^=f[nxt[i]-i-1];
}
for(int i=1;i<=n;i++)
{
s[i]=s[i-1]+t[i],lst[i]=lst[i-1];
if(t[i-1])
lst[i]=i-1;
}
for(int i=1;i+l-1<=n;i++)
{
if(s[i-1]==s[i+l-1])
{
if(!(k^f[nxt[i]-lst[i]-1]^f[nxt[i+l-1]-i-l]^f[i-lst[i]-1]))
{
// printf("%d %d\n",k^f[nxt[i]-lst[i]-1],f[nxt[i+l-1]-i-l]^f[i-lst[i]-1]);
printf("%d %d\n",i,l);
for(int j=i;j<i+l;j++)
t[j]=1;
break;
}
}
}
fflush(stdout);
}
}
}