A. Alice and Bob (game? Thinking & Violence) (2021 Niuke summer multi school training camp 1)

Portal

  The question ：Alice First of all , And Bob Take turns to pick up stones , Take it out of a pile of stones at a time k(k>0) A stone is taken out of another pile k*s(s>=0) Stone . Who can't operate, who loses the game .

Ideas ： To be honest, I don't know how to write this game , It's said that many people in the game have played this question ( It's amazing ). After the game, I found out that this problem can be solved by violence .

We initialize the tag f[i][j] ==1 Indicates that the initial two piles of stones are i and j It is a must win state , On the contrary, it is a necessary state . And then we enumerate i and j, Then enumerate k and s Handle f[i+k][j+k*s] and f[i+k*s][j+k] ( Because the initial exchange state of the two piles of stones is the same ).

Finally, pay attention to the duration of the input / output card .

Code implementation ：

#include<bits/stdc++.h>
using namespace std;
const int  N = 5010;

inline void read(int &x){
    char t=getchar();
    while(!isdigit(t)) t=getchar();
    for(x=t^48,t=getchar();isdigit(t);t=getchar()) x=x*10+(t^48);
}

int T = 1, n, m;
bool f[N][N];

int main()
{
    for(int i = 0; i <= 5000; i ++){
        for(int j = 0; j <= 5000; j ++){
            if(!f[i][j]){
                for(int k = 1; i+k <= 5000; k ++)
                    for(int s = 0; j+k*s <= 5000; s ++)
                        f[i+k][j+k*s] = 1;
                for(int k = 1; j+k <= 5000; k ++)
                    for(int s = 0; i+k*s <= 5000; s ++)
                        f[i+k*s][j+k] = 1;
            }
        }
    }

    read(T);

    while(T --){
        read(n); read(m);
        if(f[n][m]) puts("Alice");
        else puts("Bob");
    }

    return 0;
}