NYOJ练习题 又见Alice and Bob
又見Alice and Bob
時(shí)間限制：1000?ms ?|? 內(nèi)存限制：65535?KB 描述集訓(xùn)生活如此乏味，于是Alice和Bob發(fā)明了一個(gè)新游戲。規(guī)則如下：首先，他們得到一個(gè)集合包含n個(gè)特定的整數(shù)，接著他們輪流做以下操作，每一次操作，Alice或者Bob（輪到誰就是誰）會(huì)從集合中選擇兩個(gè)整數(shù)x?和?y?，（但是集合中不能包含|?x?-?y|），接著他就會(huì)把整數(shù)|x?-?y|?加入集合，因此，集合中的數(shù)據(jù)多加了一個(gè)……
如果當(dāng)前玩家不能執(zhí)行操作了，他就輸了。問題是如果Alice和Bob都很聰明的情況下，誰能獲勝呢？Alice是首先執(zhí)行操作。
輸入第一行一個(gè)整數(shù)n( n <= 110)，初始集合包含元素的個(gè)數(shù)
第二行依次輸入n個(gè)數(shù)a1，a2……an，（1 <= ai <= 10^9）以空格分開,代表集合元素。
如果Alice 獲勝輸出 “Alice”，否者輸出“Bob”
樣例輸入看起來像博弈題，其實(shí)和博弈沒有一點(diǎn)關(guān)系。給一個(gè)原始集合，每次操作都會(huì)往集合中加入一個(gè)新的元素，找出最后集合中元素的個(gè)數(shù)total，然后用 total-n 就是新加進(jìn)去的元素個(gè)數(shù)。判斷total-n 的奇偶性就可以判斷出誰贏了。如何求total呢？如果開始時(shí)集合中只有2個(gè)數(shù)6 ?27，通過這兩個(gè)數(shù)可以加進(jìn)集合的數(shù)有21 ?15 ?9 ?3，這個(gè)過程實(shí)際上就是求gcd（6,27）的過程，最小的數(shù)就是gcd(6,27)=3,還發(fā)現(xiàn)集合中的元素都是3的倍數(shù)，那我們只需要判斷[1,27]之間3的倍數(shù)有多少個(gè)就行了。 ?解法：求出n個(gè)數(shù)中的最大值Max和這n個(gè)數(shù)的最大公約數(shù)p，判斷（Max / p — n）的 ?奇偶性即可。奇數(shù)Alice贏。
#include<stdio.h> int gcd(int a, int b) {int r;while(b != 0){r = a % b;a = b;b = r;}return a; } int main() {int n, a[120], i;while(~scanf("%d",&n)){int Max = 1;for(i = 0; i < n; i++){scanf("%d", &a[i]);if(a[i] > Max)Max = a[i];}int p = a[0]; for(i = 1; i < n; i++)p = gcd(p, a[i]);int ans = Max/p - n;printf(ans&1 ? "Alice\n" : "Bob\n");}return 0; }
總結(jié)
以上是生活随笔為你收集整理的NYOJ练习题 又见Alice and Bob的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 50道Java集合经典面试题
- 下一篇： 漫话：如何给女朋友解释华为鸿蒙OS是怎样