hdu3544 Alice's Game

Alice's Game

Time Limit: 2000/2000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)

Total Submission(s): 365 Accepted Submission(s): 149

Problem Description

Alice and Bob have got a lot of chocolates. All the chocolates are rectangles of different shapes as Xi * Yi.They decide to play an interesting game on the chocolates. They take turns choose a chocolate and split it into two pieces. The one who can not take operations lose. Due to the game is too simple, the additional rules apply. Alice is only allowed to split the chocolate vertically, and Bob is only allowed to split the chocolate horizontally.

Specifically, for Alice, a chocolate Xi * Yi, can only split into A * Yi, and B * Yi where A + B = Xi and A, B > 0. And for Bob, a chocolate Xi * Yi, can only split into Xi * A, and Xi * B where A + B = Yi and A, B > 0.

Alice and Bob are clever enough to take the optimal operation, if Alice plays first, your are to decide who will win.

Input

The input contains multiple test cases. The first line of input contains a single integer denoting the number of test cases.

For each test case, the first line contains an integer N, the number of pieces of chocolates. (1 <= N <= 100)

For the next N lines, each line contains two integers Xi and Yi, denoting the chocolate sized Xi * Yi. (1 <= Xi, Yi <= 1000000000)

Output

For each test cases, output "Alice" when Alice will win, and "Bob" otherwise. See sample test cases for further details.

Sample Input

1 1

2 1

2 2

2 1

3 2

Sample Output

Case 1: Bob

Case 2: Alice

Case 3: Alice

Case 4: Bob

这题就是找最优策略,我们知道,如果对于一个n*n的块,先切的人,就是给后切的人多了一次的切的数目,所有后面的人的最优策略就是切,先切的人切下来的块,这样总次数最多,所以对于先切的人,就要想,自已怎么切才能减少对方增加的次数呢,当然就是按半来切,这样,对方所能增加的次数也会减少了!

#include <iostream>  
#include <stdio.h>  
#include <string.h>  
using namespace std;  
  
int main()  
{  
    int n,i,tt=1,tcase;  
    scanf("%d",&tcase);  
    while(tcase--){  
        scanf("%d",&n);  
       __int64 l1=0,l2=0,x,y;  
       for(i=0;i<n;i++){  
           scanf("%I64d%I64d",&x,&y);  
           while(x>1&&y>1){  
               x>>=1;y>>=1;  
           }  
           if(x>1)l1+=x-1;  
           else if(y>1) l2+=y-1;  
       }  
       printf("Case %d: ",tt++);  
       if(l1>l2)printf("Alice\n");  
       else printf("Bob\n");  
    }  
    return 0;  
}

补充：软件开发 , C++ ,