Alternative Game
National Olympiad — Municipal round (2018 season)
Submission name: altgame.cpp
Problem summary
Two players alternately remove exactly a or exactly b objects from a pile, whenever possible. A player with no legal move loses. For each extremely large initial pile, identify the winning player under optimal play.
Input
a b; m; then m decimal pile sizes.
Output
For each game, 1 if the first player wins, otherwise 2.
Constraints
1 ≤ a,b ≤ 100; 1 ≤ m ≤ 10; positive pile sizes have at most 1000 decimal digits.
Worked example
Official sample, transcribed with whitespace restored from the PDF.
Input
2 5 4 6 17 29 41
Output
1 1 2 1
Solution analysis
- Order the moves so a≤b. Compute the usual winning-state recurrence for pile sizes 0 through a+b−1: a state wins exactly when one available move reaches a losing state. The resulting table repeats with period a+b.
- To see why this finite table extends, imagine its indices on a circle of size a+b. The two possible predecessors are separated by a+b, so subtracting b is the same circular step as adding a. For n<a, both wrapped predecessors a+n and b+n are winning since each can move to the losing n. For a≤n<b, the unavailable b move wraps to n+a: whenever n is losing, n+a is winning by an a move to n; a winning n already has a legal losing predecessor. For n≥b neither move wraps. Thus the circular recurrence agrees everywhere with the table.
- Reduce each input string modulo a+b using decimal long division and consult its table entry. For moves 2 and 5, the seven entries are losing, losing, winning, winning, losing, winning, winning. The inputs 6,17,29,41 reduce to 6,3,1,6 and yield winners 1,1,2,1.
Why it works
The described wraparound argument shows that the periodic extension satisfies win[n]=not win[n−a] or not win[n−b] whenever the corresponding move is legal; the initial n<a entries are losing. Induction on n gives equality with the true game recurrence. Decimal reduction preserves the residue, so each query uses the correct periodic entry.
Watch out. Do not convert a thousand-digit pile to an integer. Zero is a losing residue, but some positive multiples of the period also have that residue.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: The described wraparound argument shows that the periodic extension satisfies win[n]=not
// win[n−a] or not win[n−b] whenever the corresponding move is legal; the initial n<a entries are
// losing. Induction on n gives equality with the true game recurrence.
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
int a,b,games;
cin>>a>>b>>games;
if(a>b){
swap(a,b);
}
int period=a+b;
vector<bool>win(period,false);
for(int n=0;n<period;++n){
win[n]=(n>=a&&!win[n-a])||(n>=b&&!win[n-b]);
}
while(games--){
string pile;
cin>>pile;
int residue=0;
for(char c:pile){
residue=(residue*10+c-'0')%period;
}
cout<<(win[residue]?1:2)<<'\n';
}
}