“This is the 19th day of my participation in the Gwen Challenge in November. See details: The Last Gwen Challenge in 2021”.

The assorted game

Introduction to the

There are nn objects in a pile, if there are two people. A and B take turns to choose 1 ~ m1\ SIM m1-m items from the pair. The last one who takes all the items wins, that is, the one who does not take all the items loses.

Train of thought

If first, set the current item number to RRR.

When r≤ Mr \le Mr ≤m, A can take it all at once and win.

When r=m+1r=m+1r=m+1, a loses whatever it takes.

When m+2≤r≤2mm+2\le r\le 2mm+2≤r≤2m, PARTY A can take r−(m+1)r-(m+1)r−(m+1), so that no more than MMM is left after Party B takes away the number, party A wins.

Based on the above process, it’s not hard to see that in order for you to win, you have to make sure that the other side gets as many m+1m+1m+1 as possible. If a wins, n%(m+1)≠0n\%(m+1)\ne 0n%(m+1)=0.

In other words, if the second player wins, NNN is a multiple of m+1m+1m+1.

Algorithm template

bool bash(int n,int m){// This returns whether the first player can win
	if(n%(m+1)) return true;
	else return flase;
}
Copy the code

sample

hdu1846

To summarize, there is a TTT group sample, each group has a NNN and MMM meaning see the beginning of this article, output the first person first hand who can win, output the winner (first or second).

#include <iostream>
using namespace std;
bool bash(int n,int m){
	if(n%(m+1)) return true;
	else return false;
}
int main(a){
	int T,n,m;
	cin>>T;
	while(T--){
		cin>>n>>m;
		if(bash(n,m)) cout<<"first\n";
		else cout<<"second\n";
	}
	return 0;
}
Copy the code

To promote

If the rule is that whoever finishes first loses, then the strategy needs to be reconsidered.

When r≤m+1r\le m+1r≤m+1, A can leave only 111 to B, and A wins.

When r=m+2r=m+2r=m+2, no matter how much a takes, B can leave only one for A, and A loses.

When m + 3 r 2 m + 2 m + 3 or less or less \ \ le le r 2 m + 2 m + 3 r 2 m + 2 or less, or less a take r – (m + 2) r – r (m + 2) – (m + 2), second from the left of the m + 2 m + 2 m + 2 will lose.

When r=2m+3r=2m+3r=2m+3, USER A loses.

Summing rules known (n – 1) % (m + 1) indicates a 0 (n – 1) (m + 1) \ \ % 0 ne (n – 1) % (m + 1)  = 0 wins, or b.

Algorithm template

bool bash(int n,int m){// This returns whether the first player can win
	if((n- 1)%(m+1)) return true;
	else return flase;
}
Copy the code