Alice and Bob (2021 Niuke summer multi school training camp 1)

Alice and Bob

2021 Niuke summer multi school training camp 1 The first question is , I didn't do it at that time , Read this blogger's blog , I understand instantly.
Topic link ：https://ac.nowcoder.com/acm/contest/11166/A
source ： Cattle from

Title Description
Alice and Bob like playing games. There are two piles of stones with numbers n and m. Alice and Bob take turns to operate, each operation can take away k(k>0) stones from one pile and take away s×k(s≥0) stones from another pile. Alice plays first. The person who cannot perform the operation loses the game.

Please determine who will win the game if both Alice and Bob play the game optimally.
Input description :
The first line contains an integer T(1≤T≤10^4 ) denotes the total number of test cases.
Each test case contains two integers n,m(1≤n,m≤5×10^ 3) in a line, indicating the number of two piles of stones.
Output description :
For each test case, print “Alice” if Alice will win the game, otherwise print “Bob”.
Example 1
Input
Copy
5
2 3
3 5
5 7
7 5
7 7
Output
Copy
Bob
Alice
Bob
Bob
Alice
The main idea of the topic :
A game of two , Each time one person takes one from the pile , At the same time, take it away from another pile k*s individual , Ask who can take it first ;
Ideas :
enumeration , violence , In fact, the idea is very simple , If you can take all the stones in one operation, you will win at this time , We use a two-dimensional array f[i][j] To indicate that the number of stones in the first pile is i The number of stones in the second pile is j The situation of ,f[i][j]=1 Indicates that the state faces two piles of stones, and the number is i,j You can take all the stones in one step ,f[i][j]=0 Indicates that the state faces two piles of stones, and the number is i,j You can't take all the stones at once . According to the title f[k][sk] or f[sk][k] It must be able to take it all at once , So enumeration s And k Find out the status of all the first to win

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <math.h>
#include <string.h>
using namespace std;
bool f[5001][5001];
int main()
{
    
    for(int i=0;i<=5000;i++)
    {
    
        for(int j=0;j<=5000;j++)
        {
    
            if(f[i][j]==0)
            {
    
                for(int k=1;k+i<=5000;k++)
                {
    
                    for(int s=0;s*k+j<=5000;s++)
                        f[i+k][j+s*k]=1;
                }
                for(int k=1;k+j<=5000;k++)
                {
    
                    for(int s=0;s*k+i<=5000;s++)
                        f[i+s*k][j+k]=1;
                }
            }
        }
    }
    int t,n,m;
    cin>>t;
    while(t--)
    {
    
        scanf("%d%d",&n,&m);
        if(f[n][m]==0)
            cout<<"Bob"<<endl;
            else
                cout<<"Alice"<<endl;
    }
}