Proficient.
Put your skills to the test.

Problem summary

Players alternate removing stones. With remainder 0 modulo 3 they may remove 1 or 2; with remainder 1, 1 or 3; with remainder 2, 1,2 or 3. A move cannot take more stones than remain. The player taking the last stone wins. Determine the winner under optimal play for each initial pile.

Constraints

2 ≤ N ≤ 100; 1 ≤ M ≤ 1000000.

Worked example

An independently prepared example for this explanation.

3
2 3 5

121

Solution analysis

1. Let win[x] indicate whether the player to move can force a win with x stones. The empty pile is losing. A positive pile is winning exactly when some allowed removal leads to a losing pile.
2. Read all queries and fill win from 1 to the largest queried pile. Each transition uses at most three smaller states, so the full bound of one million is inexpensive.
3. For 2 stones taking both wins. For 3, either move leaves a winning pile (2 or 1), so 3 loses. For 5, remove 2 to leave the losing pile 3.

Why it works

Induct on pile size. All legal moves reach smaller piles, whose results are already correct. A move to a losing state forces victory; if no such move exists, every move allows the opponent to force victory. This proves every table entry and query answer.

Watch out. The set of allowed moves depends on the pile before removing stones. Never permit a removal exceeding the current pile.

An independently written complete program with standard headers.

#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int main(){
    // Compute the exact archive answer using the method explained above.
    int n;
    cin>>n;
    vector<int>piles(n);
    int maximum=0;
    for(int&pile:piles){
        cin>>pile;
        maximum=max(maximum,pile);
    }
    vector<bool>win(maximum+1,false);
    for(int pile=1;pile<=maximum;pile++){
        for(int take=1;take<=3&&take<=pile;take++){
            bool allowed=take==1||(take==2&&pile%3!=1)||(take==3&&pile%3!=0);
            if(allowed&&!win[pile-take]){
                win[pile]=true;
            }
        }
    }
    for(int pile:piles){
        cout<<(win[pile]?'1':'2');
    }
    cout<<'\n';
}