Proficient.
Put your skills to the test.

Problem summary

A positive integer is special when its square, written without leading zeros, uses exactly the digits 0,4,9, each at least once. Sort special integers increasingly and return the N-th, counting from 1.

Source clarification. Bounded-catalogue dependency: the 32 primitive constants come from the official author source special/author/special.cpp in https://infos.infosbg.com/files/Contests/NOI-3/2009/day2/AB/problems/special.zip. No universal completeness proof for the catalogue is claimed. Candidate squares are validated exactly, and released tests plus a brute-force initial prefix are checked separately.

Constraints

1 ≤ N ≤ 250.

Worked example

An independently prepared example for this explanation.

12

20102

Solution analysis

1. Multiplication of a root by 10 appends two zero digits to its square. Thus a primitive root with only 4 and 9 in its square becomes special after at least one appended zero; a primitive root whose square already contains all three digits stays special after any number of appended zeros.
2. This bounded solution explicitly depends on the finite primitive-root catalogue in the official 2009 reference solution, rather than claiming a general classification of such squares. Generate all its zero-shifted candidates with at most 17 decimal digits, validate each square using exact decimal multiplication, deduplicate, and sort. The catalogue supplies at least the first 250 entries required by the task.
3. The first entries are 70,97,700,970,997,2120,3148,7000,9700,9970,9997,20102, so N=12 returns 20102. Exact digit validation excludes unshifted 7 and 212 because their squares omit zero. The 250-th generated entry is 99999997000000000.

Why it works

For each catalogue root, appending k zeros multiplies its square by 10^(2k), so generated candidates have exactly the claimed squared digits when they pass the explicit validator. Sorting and deduplicating therefore gives the increasing sequence represented by the official bounded catalogue. Completeness for the original N≤250 is a dependency on that published reference catalogue; this solution does not provide or claim an independent universal completeness theorem.

Watch out. Do not square a 17-digit root in 64-bit arithmetic. This implementation uses decimal digit multiplication. The catalogue is specific to the original N≤250 bound and must not be extrapolated as a proven infinite classification.

An independently written complete program with standard headers.

#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
using namespace std;
bool special(long long root){
    string digits=to_string(root);
    reverse(digits.begin(),digits.end());
    vector<int>square(2*digits.size()+1,0);
    for(size_t i=0;i<digits.size();i++){
        for(size_t j=0;j<digits.size();j++){
            square[i+j]+=(digits[i]-'0')*(digits[j]-'0');
        }
    }
    for(size_t i=0;i+1<square.size();i++){
        square[i+1]+=square[i]/10;
        square[i]%=10;
    }
    while(square.size()>1&&square.back()==0){
        square.pop_back();
    }
    int mask=0;
    for(int digit:square){
        if(digit==0){
            mask|=1;
        }
        else if(digit==4){
            mask|=2;
        }
        else if(digit==9){
            mask|=4;
        }
        else{
            return false;
        }
    }
    return mask==7;
}
int main(){
    int n;
    cin>>n;
    // Finite primitive catalogue from the official NOI 2009 special reference.
    const vector<long long>primitive={20000000100000002LL,200000010000002LL,2000001000002LL,
        20000100002LL,200010002LL,2001002LL,20102LL,212LL,2121179131852LL,3074003LL,953671853653LL,
        99704560597822753LL,7LL,6328428636000007LL,2118984413357LL,97LL,997LL,9997LL,99997LL,999997LL,
        9999997LL,99999997LL,999999997LL,9999999997LL,99999999997LL,999999999997LL,9999999999997LL,
        99999999999997LL,999999999999997LL,9999999999999997LL,99999999999999997LL,3148LL};
    const long long limit=99999999999999999LL;
    vector<long long>sequence;
    for(long long root:primitive){
        while(true){
            if(special(root)){
                sequence.push_back(root);
            }
            if(root>limit/10){
                break;
            }
            root*=10;
        }
    }
    sort(sequence.begin(),sequence.end());
    sequence.erase(unique(sequence.begin(),sequence.end()),sequence.end());
    cout<<sequence[n-1]<<'\n';
}