Proficient.
Put your skills to the test.

Problem summary

An infinite binary tree starts at label 1. The children of label x are p·x and p·x+1. For each of four queries n, decide whether n is expressible in exactly one way as the sum of two different tree labels; swapping the summands does not create a new way.

Constraints

2 < p < 50; 0 < each query < 10^18.

Worked example

Original statement sample.

3 7 28 13 9

1 1 0 0

Solution analysis

1. Tree labels are exactly positive base-p numbers containing only digits 0 and 1: taking a left or right edge appends that digit. Adding two such labels produces only digits 0,1,2. Since p>2 there are no carries, so any larger digit rules out a representation.
2. A result digit 2 forces a 1 in both summands. Each result digit 1 must be assigned to exactly one summand. Let r count the 1-digits. If a 2-digit exists, both summands are already nonzero; there are 2^r ordered assignments, paired by swapping, except r=0 gives two identical forbidden labels. Uniqueness therefore means r=1.
3. With no 2-digit, assignments giving a zero summand must be excluded. For r≥1 the unordered count is 2^(r−1)−1, so uniqueness means r=2. We only need these two small conditions, never the exponential count itself.
4. For p=3, 7 is 21 in base 3: the 2 forces 3+3 and the 1 goes to one side, giving 3+4. The number 28 is 1001 in base 3, uniquely 27+1. The number 13 is 111 and has three representations; 9 is 100 and cannot split into two nonzero labels.

Why it works

Carry-free base-p addition gives a bijection between valid summand pairs and the per-digit assignments described above. Enforcing nonzero and unequal summands leaves exactly the stated assignment counts, whose value is one precisely in the two tested cases.

Watch out. The tree is infinite: do not generate its vertices. Summands must be different and nonzero. Digits 2 are allowed in the sum even though tree labels themselves use only 0 and 1; p>2 is what prevents carries.

An independently written complete program with standard headers.

#include<iostream>
using namespace std;
bool uniqueSum(long long value,int base){
    int ones=0;
    bool hasTwo=false;
    while(value>0){
        int digit=static_cast<int>(value%base);
        if(digit>2){
            return false;
        }
        if(digit==1){
            ones++;
        }
        if(digit==2){
            hasTwo=true;
        }
        value/=base;
    }
    // A 2-digit already makes both summands positive.
    return hasTwo?ones==1:ones==2;
}
int main(){
    int base;
    cin>>base;
    for(int query=0;query<4;query++){
        long long value;
        cin>>value;
        if(query>0){
            cout<<' ';
        }
        cout<<uniqueSum(value,base);
    }
    cout<<'\n';
}