Intermediate.
Put your skills to the test.

Problem summary

Starting with a, each stage inserts the next letter at both ends and between every pair of old letters. Find position p after stage n, or 0 if out of range.

Constraints

1 ≤ n ≤ 26; 1 ≤ p < 10^9; positions are 1-based.

Worked example

Input and output for the worked example discussed below.

4 10

c

Solution analysis

1. After stage n, the sequence length is 2^n−1. Newly inserted copies of the nth letter occupy odd positions, while old position q moves to even position 2q.
2. If p is outside the final length, print 0. Otherwise an odd p identifies the current stage letter. For even p, divide p by 2 and reduce the stage by one to locate the same old character.
3. For n=4,p=10, go back to stage 3,p=5. That position is odd, so it holds the third letter c. This avoids constructing a string that can contain over 67 million letters.

Why it works

The insertion rule places new letters exactly at odd indices and preserves the preceding stage at even indices. Every backward division therefore preserves the requested character’s identity until its insertion stage is reached.

Watch out. Check length before indexing. Use integer shifts for powers of two, and keep positions 1-based.

An independently written complete program with standard headers.

#include<iostream>
using namespace std;
int main(){
    int stage;
    long long position;
    cin>>stage>>position;
    long long length=(1LL<<stage)-1;
    if(position>length){
        cout<<"0\n";
        return 0;
    }
    // Even positions map directly to the previous construction stage.
    while(position%2==0){
        position/=2;
        stage--;
    }
    cout<<char('a'+stage-1)<<'\n';
}