Alice and Bob

桃扇骨 2023-07-08 05:52 13阅读 0赞

**Alice and Bob are playing a stone game in a board of n×m cells.**  
In the begining, the stone is in the upperleft cell. And in each turn, they can move the stone one cell to the right or one cell down, or diagonally k cells down to the right, which means if you are at (x,y), then you could move into (x+1,y), (x,y+1) or (x+k,y+k) at the next step. The player who can not move loses. They play in turns and Alice moves first.

Now given n, m and k, could you tell me who is the winner?  
**Input**  
First line contains an integer T(1≤T≤10), denoting the number of test cases.

In each test case, the first line is two integers Q and k.  
In the following Q lines, each line contains n and m.(1≤Q≤1000,1≤k,n,m≤109)  
**Output**  
For each test case, output Q lines.  
If Alice is the winner, output `Alice''. Otherwise`Bob’’.  
**Sample Input**

2
    2 1
    4 5
    3 4
    2 3
    4 5
    5 6

**Sample Output**

Alice
    Alice
    Alice
    Bob

import java.util.Scanner;
    public class Alice_Bob {
        
        public static void main(String[] args) {
        
            int T;
            Scanner sc=new Scanner(System.in);
            T=sc.nextInt();
            while(T>0)
            {
        
                T--;
                int q, k;
                q=sc.nextInt();
                k=sc.nextInt();
                while(q>0)
                {
        
                    q--;
                    int n, m, t;
                    n=sc.nextInt();
                    m=sc.nextInt();
                    if(n < m)//由于表是关于主对角线对称的，为了判断方便让m保持是n和m中比较小的那个值。
                    {
        
                        t = n;
                        n = m;
                        m = t;
                    }
                    if(k == 1)
                    {
        
                        if(m % 2!=0)
                        {
        
                            if((n - m) % 2!=0)
                                System.out.println("Alice");
                            else
                                System.out.println("Bob");
                        }
                        else
                        {
        
                              System.out.println("Alice");
                        }
                    }
                    else
                    {
        
                        t = 2 * (k + 1);//循环周期
                        if((m % t >= 1) && (m % t <= k))
                        {
        
                            if((n - m) % 2!=0)
                                System.out.println("Alice");
                            else
                                System.out.println("Bob");
                        }
                        else if(m % (k + 1)==0)
                            System.out.println("Alice");
                        else
                        {
        
                            if((n - m) % 2!=0)
                                System.out.println("Bob");
                            else
                                System.out.println("Alice");
                        }
                    }
                }
            }
        }
    }

# 打表 #

public class meiri {
        
        public static int[][][]sg=new int[110][110][110];
        public static int getsg(int n,int m,int k){
        
            if (n==1&&m==1){
        
                return sg[n][m][k]=1;
            }
            if (sg[n][m][k]!=0){
        
                return sg[n][m][k];
            }
            int flag=1;
            if(n-1>=1)
            {
        
                if(getsg(n-1,m,k)==1)
                {
        
                    flag=2;
                }
            }
            if(m-1>=1)
            {
        
                if(getsg(n,m-1,k)==1)
                {
        
                    flag=2;
                }
            }
            if(k!=0)
            {
        
                if(n-k>=1&&m-k>=1)
                {
        
                    if(getsg(n-k,m-k,k)==1)
                    {
        
                        flag=2;
                    }
                }
            }
            return sg[n][m][k]=flag;
        }
        public static void main(String[] args) {
        
    
            for (int k = 1; k <=10 ; k++) {
        
                System.out.println(k);
                for (int n = 1; n <=10 ; n++) {
        
                    for (int m = 1; m <=10; m++) {
        
                        sg[n][m][k]=getsg(n,m,k);
                        System.out.print(sg[n][m][k]==2?"1 ":"0 ");
                    }
                    System.out.println();
                }
            }
        }
    }

# 1是Alice赢哦！ #

![在这里插入图片描述][20200423144927882.png]

[20200423144927882.png]: https://img-blog.csdnimg.cn/20200423144927882.png