The idea is notice that the string cannot be bigger than 64 characters due to constraints.

You calculate how big the length of the string should be – say L.

Then you generate a string of length L and set only 5s.

Then iterate and change the 5 to a 6. Find how many numbers are smaller after the change. If count is bigger than K (the index we are searching for), then we should change it back to 5.

Finding the number of smaller numbers is easy. Say that we have generated so far:

Number = 565

Then obviously all numbers of length 2 and 1 are smaller. Namely:

length 1. Numbers are 5 and 6. => Count is 2 which is 1< <1.
length 2. Numbers are 55,56,65,66 => count is 4 which is 1< <2
=> in general for length L, the count of smaller ones are 2^1 + 2^2 + .. + 2^ (L-1)

Then we have to take in hand all numbers of length L=3. We iterate over the string until we find a 6 and then compute.

In our case, 5**6**5.

Then obviously we have the suffix 5, for which we can set whatever 5 or 6. => we have a count of 2^(suffix length).

Solution:

#include <iostream> using namespace std; typedef unsigned long long ull; ull pow[65]; ull sum[65]; int calcLen(ull num) { for (int i = 1; i <= 64; ++i) { if (sum[i] >= num) return i; } return 64; } ull calcSmaller(int len, char * buf) { ull cnt = sum[len-1]; for (int i = 0; i < len; ++i) { if (buf[i] == '6') { cnt += pow[len-i-1]; } } return cnt; } void gen(ull num, int len, char * buf) { for (int i = 0; i < len; ++i) buf[i] = '5'; buf[len] = '\0'; for (int i = 0; i < len; ++i) { buf[i] = '6'; if (calcSmaller(len, buf) >= num) { buf[i] = '5'; } } } int main() { cin.sync_with_stdio(0); for (int i = 1; i<=64; ++i) { pow[i] = 1ULL<<i; sum[i] = sum[i-1] + pow[i]; } pow[0] = 1ULL; int n; cin >> n; ull num; char buf[65]; while (n--) { cin >> num; int len = calcLen(num); gen(num, len, buf); cout << buf << endl; } return 0; }