CF346A Alice and Bob

    • 32通过
    • 52提交
  • 题目来源 CodeForces 346A
  • 评测方式 RemoteJudge
  • 标签
  • 难度 提高+/省选-
  • 时空限制 2000ms / 256MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    Alice与Bob发明了一种游戏。给出n个不同的正整数,两人轮流做以下操作:

    1. 从序列中选出两个数$x,y$,要求这两个数的差的绝对值$|x-y|$不在序列中
    2. 将这两个数的差的绝对值$|x-y|$加入序列

    当有一方无法完成这个操作时,即失败。Alice先手,两方均选择最优策略,问哪方将获胜。

    输入

    第一行为一个整数$n$,表示数字个数。 第二行为n个以空格分隔的数,代表初始的$n$个数字。

    输出

    输出获胜者的名字,“Alice”或“Bob”。

    题目描述

    It is so boring in the summer holiday, isn't it? So Alice and Bob have invented a new game to play. The rules are as follows. First, they get a set of $ n $ distinct integers. And then they take turns to make the following moves. During each move, either Alice or Bob (the player whose turn is the current) can choose two distinct integers $ x $ and $ y $ from the set, such that the set doesn't contain their absolute difference $ |x-y| $ . Then this player adds integer $ |x-y| $ to the set (so, the size of the set increases by one).

    If the current player has no valid move, he (or she) loses the game. The question is who will finally win the game if both players play optimally. Remember that Alice always moves first.

    输入输出格式

    输入格式:

    The first line contains an integer $ n $ ( $ 2<=n<=100 $ ) — the initial number of elements in the set. The second line contains $ n $ distinct space-separated integers $ a_{1},a_{2},...,a_{n} $ ( $ 1<=a_{i}<=10^{9} $ ) — the elements of the set.

    输出格式:

    Print a single line with the winner's name. If Alice wins print "Alice", otherwise print "Bob" (without quotes).

    输入输出样例

    输入样例#1: 复制
    2
    2 3
    
    输出样例#1: 复制
    Alice
    
    输入样例#2: 复制
    2
    5 3
    
    输出样例#2: 复制
    Alice
    
    输入样例#3: 复制
    3
    5 6 7
    
    输出样例#3: 复制
    Bob
    

    说明

    Consider the first test sample. Alice moves first, and the only move she can do is to choose 2 and 3, then to add 1 to the set. Next Bob moves, there is no valid move anymore, so the winner is Alice.

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。