So, here’s the question:

We consider a positive integer perfect, if and only if the sum of its digits is exactly 10. Given a positive integer k, your task is to find the k-th smallest perfect positive integer.

Input: A single line with a positive integer k (1≤k≤10000).

Output: A single number, denoting the k-th smallest perfect integer.

The solution I’ve got for this question is:

int main(){
    int k=0, m=19, c=0, sum=0;
    scanf("%d", &k);
    while(true){
        int n = m;
        sum = 0;
        while(n){
            sum+=n%10;
            n=n/10;
        }
        // printf("%d %d %dn", n, sum, c);
        if(sum == 10) c++;
        if(c == k) break;
        m++;
    }
    printf("%d", m);
    return 0;
}

So, isn’t there any solution that is more efficient than this one ?

I’ve thought about this problem for about an hour and then decided to google the answer. This solution truly disappointed me. I’ve expected that there will be some tricky math hidden in this problem.