Proficient.
Put your skills to the test.

Problem summary

Players alternately delete the rightmost digit of the current number in base 2 (move 1) or base 10 (move 2). The other representation is then synchronized with the shortened one. Deleting the final digit wins immediately. For each of four starting numbers choose a winning first move, or let the opponent start if the position is losing.

Source clarification. The statement’s synchronization sentence names the unedited representation, but its worked play clearly synchronizes from the edited one. This explanation follows the demonstrated game. The implementation also safely accepts 0 if included in the source’s convention for natural numbers.

Constraints

Each starting number has at most 60 decimal digits.

Worked example

Original statement sample.

31
9
5000
65001

1202

Solution analysis

1. Deleting a binary digit divides the value by 2 with the remainder discarded. Deleting a decimal digit divides it by 10. A one-digit decimal number is immediately winning by move 2; 0 and 1 also have a one-digit binary representation.
2. A larger state is winning exactly when at least one child is losing. Memoize states as normalized decimal strings, implement division by 2 by a left-to-right carry scan, and obtain division by 10 by removing the last character. This handles 60 digits without nonstandard integer types.
3. For 31, moving to 15 by binary truncation is winning because 15 can only move to immediately winning one-digit numbers. The original four sample games yield 1202. Both division operations commute under flooring: every descendant is floor(N/(2^a·10^b)). There are only O(D²) distinct exponent pairs for D decimal digits, even though the naive game tree branches.

Why it works

Terminal states are winning because the player can remove their last digit immediately. Every nonterminal move strictly decreases the number. Induction on value therefore proves the recurrence: a move to a losing child wins, while a state whose every child wins is losing. Memoization changes only how often a state is evaluated, not its value.

Watch out. Do not use 64-bit integers for 60-digit inputs. Synchronize from the edited representation; otherwise the move would be undone, contrary to the example. Stop immediately when a representation becomes empty rather than treating an empty string as a normal game state.

An independently written complete program with standard headers.

#include<iostream>
#include<string>
#include<unordered_map>
using namespace std;
unordered_map<string,bool>memo;
string half(const string&number){
    string result;
    int carry=0;
    for(char digit:number){
        int current=carry*10+digit-'0';
        int quotient=current/2;
        if(!result.empty()||quotient!=0){
            result.push_back(static_cast<char>('0'+quotient));
        }
        carry=current%2;
    }
    return result.empty()?"0":result;
}
bool winning(const string&number){
    if(number.size()==1){
        return true;
    }
    auto found=memo.find(number);
    if(found!=memo.end()){
        return found->second;
    }
    // Integer truncations form an acyclic game graph.
    bool answer=!winning(half(number))||!winning(number.substr(0,number.size()-1));
    memo[number]=answer;
    return answer;
}
int main(){
    for(int game=0;game<4;game++){
        string number;
        cin>>number;
        memo.clear();
        if(number=="0"||number=="1"){
            cout<<1;
        }
        else if(number.size()==1){
            cout<<2;
        }
        else if(!winning(half(number))){
            cout<<1;
        }
        else if(!winning(number.substr(0,number.size()-1))){
            cout<<2;
        }
        else{
            cout<<0;
        }
    }
    cout<<'\n';
}