[notes] Bashi game

Define

Bashi game is the simplest game, defined as follows

There is only a pile of n items, two people take turns from the pile of goods, the provisions of at least one at a time, a maximum of M. Finally, the winner wins.

Victory state\(N\)And must defeat state\(P\)

• All winning States\(N\)There must be a way to move to defeat.\(P\)
• Abortive state\(P\)No matter how it is transferred, it will be transferred to victory.\(N\)(Win the next battle.
• All endpoints must be defeated.\(P\)

Analysis of victory\(N\)And must defeat state\(P\)Starting from the endpoint, we analyze the reverse order.

Analyze

For victory\(N\)And must defeat state\(P\)Analysis

Now if there is a total of\(m+1\)Let’s go get it. We have to take at least one of them first, but we can’t get all of them. This leads to a win-win situation for the second hand.

If the number of things is less than or equal to the number of things that can be taken, it is triumphant, because it is taken only once, and if it is greater than the number that can be taken, we can put the total number.\(n\)Decomposed into\((m+1)∗x+r\)

Obviously,\((m+1)∗x+r\)Number, if we start, we just need to take away.\(r\)Number, then stay.\((m+1)∗x\)To each other, so that each time the other party takes a number.\(y\)We just need to take it.\(m+1−y\)One can do it, that is to say, each one.\(m+1\)The last one is from the very beginning, which ensures that if it can be decomposed into\((m+1)∗x+r\)If you can, you will win first, if you can only decompose it into\((m+1)∗x\)If you say, you will lose.

Code

[HDU2846] Brave Game

#include <iostream>
#include <cstdio>
#define sc(x) scanf("%d", &x);

using namespace std;

int main(){
    int t, n, m;
    sc(t);
    while(t--){
        sc(n);
        sc(m);
        if(n % (m + 1) == 0)
            printf("second\n");
        else 
            printf("first\n");
    }
    return 0;
}