2015
05-24

# Stone Game

Alice and Bob are playing a game. It is played in 1*N grids. Each grid can be occupied by one stone. Alice has K white stones on the left (numbered 1 to K from left to right), and Bob has K black stones on the right (numbered 1 to K from right to left). They take turns to move their own stones, and Alice moves first. In each move, the player must choose one stone to move to the nearest empty grid forward (Alice moves to the right, Bob moves to the left). If one player cannot find any stone to move, he wins.
Now Alice asks you to find a winning strategy of the game. Can you help him?

There are multiple test cases. In each case, there is one line containing two integers N, K.

Technical Specification
3 <= N <= 1,000,000, 1 < K*2 < N

There are multiple test cases. In each case, there is one line containing two integers N, K.

Technical Specification
3 <= N <= 1,000,000, 1 < K*2 < N

3 1
4 1

Case 1: Bob
Case 2: Alice 1

k=1时

很容易看出，n为奇数则后手获胜，n为偶数则先手获胜

k>1时

如果n=2*k+1，则棋 盘中只有一个空白的格子，每次移动必须移动到当前的空白格子上。先手方可以先随意选择一颗棋子占据中间的位置，然后双方互有移动，移动过程中双方肯定都会 选择一颗在己方半场的棋子移动到对方半场里。直到后手方还剩下一颗己方半场的棋子时，先手方把占据中间的棋子移动到对方半场，此时后手方必须移动剩下的这 颗棋子到空出的中间的格子里，先手方再把最后一颗棋子移动到新空出的位置即可获胜。

如果n>2*k+1，那么棋盘中就有了多余一个的 空白格子。如果n为奇数，先手方只要每次移动己方最靠后的一颗棋子即可获胜。并且第一次移动必须选择1号棋子，否则会让自己的棋子中间留下空白相当于把先 手让给了对方，这时对方只要采用先手策略即可获胜；如果n为偶数，那么先手方只需采用n=2*k+1时的策略在双方交会的时候保住先手即可，当然此时的第一步还是1号棋子，否则将失去先手优势。

#include <cstdio>
#include <algorithm>

using namespace std;

int n,k;

int main(void)
{
//freopen("input.txt","r",stdin);
int cas = 1;
while(scanf("%d %d",&n,&k)!=EOF){
printf("Case %d: ",cas++);
int r = n - 2 * k;
int ans = 1;
bool sig = true;
if(r&1){
if(k == 1) sig = false;
else if(r == 1) ans = k;
}

if(sig)
printf("Alice %d\n",ans);
else
puts("Bob");
}
return 0;
}


﻿﻿