Digit in a Recursive Sequence
National Olympiad — National round
Submission name: seq.cpp
Problem summary
Define S₁="1" and Sᵢ as the decimal representation of i followed by two copies of Sᵢ₋₁. Find its K-th digit for S_N, with positions starting at 1.
Input
N K.
Output
The requested digit, or −1 if the position does not exist.
Constraints
1 ≤ N ≤ 100,000; 1 ≤ K ≤ 10¹⁵.
Worked example
An independently prepared example for this explanation.
Input
3 5
Output
2
Solution analysis
- Compute lengths L[i]=digits(i)+2L[i−1], saturating at 10¹⁵.
- At each level first test the prefix containing i. Otherwise subtract its length, choose the first or second recursive copy, and descend.
Why it works
Each string consists of the three stated consecutive blocks. The chosen block contains exactly the queried position; saturation cannot alter a comparison to K≤10¹⁵.
Complexity: O(N log N) time for decimal conversions, O(N) space.
Watch out. Never materialize the exponentially long strings; positions are 1-based.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Each string consists of the three stated consecutive blocks. The chosen block contains
// exactly the queried position; saturation cannot alter a comparison to K≤10¹⁵.
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
int main(){
int n;
long long k;
cin>>n>>k;
const long long LIM=1000000000000000LL;
vector<long long>len(n+1);
len[1]=1;
for(int i=2;i<=n;i++){
len[i]=min(LIM,(long long)to_string(i).size()+2*len[i-1]);
}
if(k>len[n]){
cout<<-1<<'\n';
return 0;
}
while(n){
string s=to_string(n);
if(k<=(long long)s.size()){
cout<<s[k-1]<<'\n';
return 0;
}
k-=s.size();
if(k>len[n-1]){
k-=len[n-1];
}
--n;
}
}