B.T.B.F.

Description

一年一度的Be The Best Foodie(BTBF)大赛开始了。现在已经到了最终决赛。Alice和Bob这对老冤家再次相遇。那么这次,将鹿死谁手呢!

BTBF的规则如下:场上将提供一把刀,nn块蛋糕。双方轮流执刀。执刀的一方先选择一块蛋糕,将其切成两份,而另一方则选择一份蛋糕吃掉,最后,执刀手将剩下的蛋糕吃掉。为了化简比赛规则,我们将每一块蛋糕的大小化作一个正整数,而蛋糕被切开之后,分成的两个蛋糕必须依然为正整数。没有蛋糕可切之时,则结束比赛。最后,吃的最多的人获胜。

Alice和Bob都是前所未有的高智商大胃王,每次都一定会做全局于自己最优的选择。

Alice先行执刀。

那么,现在当给出每块蛋糕的大小时,请你预言比赛的结果。

Input

第一行一个整数TT,代表有TT组数据。

每组数据格式如下:

第一行一个正整数nn,代表有nn块蛋糕。

第二行n个正整数a_iai​,以空格间隔,代表每块蛋糕的大小。

\sum {n} \le 100000∑n≤100000 a_i \le 1,000,000,000ai​≤1,000,000,000

Output

每组数据输出一行。若Bob吃得多,则输出“Bob”;反之则输出“Alice”。

Sample Input 1 

3
1
2 
1
3
2
2 2

Sample Output 1

Alice
Bob
Alice

题解:对应每个人的最优解为:持刀人会优先挑偶数的蛋糕,直到无偶数蛋糕可切,之后只能切奇数蛋糕,谁切的奇数蛋糕多,谁吃的就比对方少1(如3切成1和2,那么切的人只能吃到1)

//
//  main.cpp
//
//
//  Created by Edwin on 2018-12-23.
//  Copyright © 2018 Edwin. All rights reserved.
//
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0×7ffffff
#define EPS 1e-8
#define maxn 1000000+10
#define PI acos(-1.0)
#define pb push_back
using namespace std;

int main()
{
    ll test,n,m;
    cin>>test;
    while(test--)
    {
        cin>>n;
        int ou=0;
        int ji=0;
        while(n--)
        {
            int x;
            cin>>x;
            if(x<2) continue;
            if(x%2) ji++;
            else ou++;
        }
        ou%=2;
        ji%=2;
        if(ji)
            if(ou)
                cout<<"Alice"<<endl;
            else
                cout<<"Bob"<<endl;
            else cout<<"Alice"<<endl;
    }
    return 0;
}

 

发表评论,支持MarkDown语法