Alice and Bob |
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:65536KB |
Total submit users: 20, Accepted users: 10 |
Problem 11499 : No special judgement |
Problem description |
Alice and Bob are interested in playing games. One day, they invent a game which has rules below:
Here’s the question, please tell me who will win the game if both Alice and Bob play the game optimally. |
Input |
At the beginning, an integer T indicating the total number of test
cases. Every test case begins with two integers n and m, which are described before. And on the next line are m positive integers d1,d2,..,dm. T≤100 1≤n≤10^6 1≤m≤100 1≤dk≤10^6,1≤k≤m |
Output |
For every test case, print “Case #k: ” firstly, where k indicates the
index of the test case and begins from 1. Then if Alice will win the game, print
“Alice”, otherwise “Bob”. |
Sample Input |
2 7 1 3 7 2 2 6 |
Sample Output |
Case #1: Alice Case #2: Bob |
ps:http://acm.hunnu.edu.cn/online/?action=problem&type=show&id=11499&courseid=136
【博弈:】
今天终于用到你了!
题意:Alice 和 Bob又玩游戏了,这次是这样的,看谁先超过给定的数,超过的人就输了;首先Alice
先输入s1=0;(相当于Bob优先)然后假设第 i 次的数字是 S[i] ,那么第 i+1 次的数字 S[i+1]= S[i]+d[k]或者 S[i]-d[k],条件是 S[i+1]<= n && S[i-1]<S[i+1]。比赛的时候没有“或者 S[i]-d[k]”这句话,不过这也没关系。
思路:我当时是这么想的,如果我来选,那么我肯定选最小的啊,这样离n才远,所以就选出dk里面的最小的,然后看看n/min(dk)是奇数呢还是偶数,如果是奇数Bob就win,偶数Alice就win;
加了红色的那句呢,也可以这么理解,如果我没错加min(dk),那么为了满足S[i-1]<S[i+1]那么后面的人只能加上数而不能剪数,那么又回到了上面的问题上;(ps:不能让对手减数就是要S[i]<S[i+1]这样才有赢得机会。)
#include<stdio.h> int main() { int T,n,m,ans,tp,Case; scanf("%d",&T); for(Case=1;Case<=T;Case++) { scanf("%d%d",&n,&m); int min=999999999; for(int i=0;i<m;i++) { scanf("%d",&ans); if(ans<min) min=ans; } tp=(n/min)%2; printf("Case #%d: ",Case); if(tp==0) printf("Alice "); else printf("Bob "); } return 0; }
再不理解就想想那么直接想最后一步,什么时候就结束呢?自然是s(i)+min > n 时就输了
so。。你懂了。
再不懂的话。。。。
只能恕我能力低微,,,解释不清楚了。