Alice&Brown(AtCoder-2400)

Problem Description

Alice and Brown loves games. Today, they will play the following game.

In this game, there are two piles initially consisting of X and Y stones, respectively. Alice and Bob alternately perform the following operation, starting from Alice:

Take 2i stones from one of the piles. Then, throw away i of them, and put the remaining i in the other pile. Here, the integer i (1≤i) can be freely chosen as long as there is a sufficient number of stones in the pile.
The player who becomes unable to perform the operation, loses the game.

Given X and Y, determine the winner of the game, assuming that both players play optimally.

Constraints

  • 0≤X,Y≤1018

Input

Input is given from Standard Input in the following format:

X Y

Output

Print the winner: either Alice or Brown.

Example

Sample Input 1

2 1

Sample Output 1

Brown
Alice can do nothing but taking two stones from the pile containing two stones. As a result, the piles consist of zero and two stones, respectively. Then, Brown will take the two stones, and the piles will consist of one and zero stones, respectively. Alice will be unable to perform the operation anymore, which means Brown's victory.

Sample Input 2

5 0

Sample Output 2

Alice

Sample Input 3

0 0

Sample Output 3

Brown

Sample Input 4

4 8

Sample Output 4

Alice

题意:A、B 玩游戏,开始时,有两堆石头,分别为 x、y 个,可以从一堆中选 2i 个,然后放 i 个到另一堆,当无法再进行操作时的玩家为输,每次 A 先开始操作,现在给出 x、y,要求输出获胜的人

思路:

当给出的 x、y 的值分别为 (0,0)、(0,1)、(1,0)、(1,1) 时,一定无法操作,A 必败,此时 |x-y|<=1

而当  |x-y|>1 时,可以通过任意一步,使得 x、y 的差值 |x-y|<=1

那么即有:当 |x-y|>=2 时,先手必胜,否则后手必胜

Source Program

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define EPS 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LL long long
const int MOD = 1E9+7;
const int N = 100000+5;
const int dx[] = {-1,1,0,0,-1,-1,1,1};
const int dy[] = {0,0,-1,1,-1,1,-1,1};
using namespace std;

int main() {
    LL x,y;
    scanf("%lld%lld",&x,&y);
    if(llabs(x-y)>=2)
        printf("Alice\n");
    else
        printf("Brown\n");
    return 0;
}

 

上一篇:2019安徽省赛题解


下一篇:浅谈--什么是非对称加密?(加密通信的原理)