題干：

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.

Input

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?a1,?a2,?...,?an?(1?≤?ai?≤?109) — the elements of the set.

Output

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

Examples

Input

2 2 3

Output

Alice

Input

2 5 3

Output

Alice

Input

3 5 6 7

Output

Bob

Note

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.

題目大意：

? 給你一個(gè)數(shù)的序列，定義一種操作：任選兩個(gè)不同的數(shù)，將他們的差的絕對(duì)值加入序列中（注意操作中不涉及刪除元素）。問你需要多少次操作可以操作到無法操作，如果操作次數(shù)是奇數(shù) 那就Alice贏，偶數(shù)就Bob贏，讓你輸出最后誰獲得勝利。

解題報(bào)告：

? 其實(shí)原題干不是這么寫的，，原題看起來像是個(gè)博弈問題，，但是其實(shí)分析以后不難發(fā)現(xiàn)，其實(shí)就是個(gè)操作次數(shù)的奇偶問題。（其實(shí)也可能是可以證明，給定一個(gè)初始序列之后，那么操作次數(shù)就已經(jīng)固定了，我們只需要求出這個(gè)數(shù)是奇數(shù)還是偶數(shù)就可以了。）

? 分析到這一步，然后我們從結(jié)果入手，結(jié)果序列一定是不能再操作的，我們假設(shè)這個(gè)序列是個(gè)遞增序列的話（其實(shí)他加這個(gè)絕對(duì)值的原因就是告訴你：你可以把這個(gè)序列當(dāng)成一個(gè)遞增序列去看，，因?yàn)樗砑訑?shù)了啊也沒說添加到哪里，如果默認(rèn)添加到最后，那么這個(gè)序列肯定就不是一個(gè)遞增序列了，所以他說有絕對(duì)值，就是為了讓你把它當(dāng)成一個(gè)排好序的遞增的），那么我們?nèi)我鈨身?xiàng)的差都在這個(gè)序列中，也就是說這個(gè)數(shù)列一定是一個(gè)等差數(shù)列，并且排好序后的最大項(xiàng)一定是an，那么我們能得到的最小值是多少呢？根據(jù)求gcd的原理我們知道，兩個(gè)數(shù)相減，得到的一定是兩個(gè)數(shù)的gcd的倍數(shù)。根據(jù)這個(gè)原理，我們知道最小的數(shù)一定是這n個(gè)數(shù)的gcd，求值，也就是最終序列的a[1]。現(xiàn)在我們有了最終序列的a[1]和a[all]，現(xiàn)在要求一共操作了多少次才變成這個(gè)序列。因?yàn)槊恳淮尾僮髦辉黾右粋€(gè)元素，那么增加了多少個(gè)元素，肯定就操作了多少次唄。那么增加了多少個(gè)元素呢？最終序列元素個(gè)數(shù)為all，初始序列為n個(gè)，那作差就是答案啊。然后判斷這個(gè)答案的奇偶性就可以了。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 2e5 + 5; int a[MAX]; int main() {int n;cin>>n;for(int i = 1; i<=n; i++) scanf("%d",a+i);sort(a+1,a+n+1);int g = a[1];for(int i = 2; i<=n; i++) g = __gcd(a[i],g);int tmp = a[n]/g - n;if(tmp&1) puts("Alice");else puts("Bob");return 0 ;}

?

總結(jié)

以上是生活随笔為你收集整理的【CodeForces - 347C 】Alice and Bob （思维，数学，等差数列）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。