Найдите K-е наименьшее число, сумма цифр которого равна 10.

Основная проблема вашего кода заключается в том, что вы ограничиваете поиск значений меньше 20000.

Для повышения эффективности я добавил два трюка

• Я избегаю повторения одних и тех же вычислений несколько раз, запоминая предыдущие результаты.
• По значению суммы цифр подстраиваю значение приращения

На моем ПК для вычисления максимального значения (для k = 20000) требуется 0,15 с.

Дополнительные пояснения

В коде переменная i соответствует кандидатам, то есть значениям, которые мы проверяем, равна ли сумма цифр 10 или нет.

num соответствует индексу найденных решений. Решение соответствует числу, сумма цифр которого равна 10. mem[num] = i означает, что i является num^th решением. k имеет то же значение, что и в коде OP: мы хотим найти число k^th такое, что сумма цифр = 10.

Две строки int kmax = 1; mem[1] = 19; используют тот факт, что 19 является первым допустимым решением. Это нужно для инициализации управления вектором mem, который запоминает все найденные решения.

Уловки, используемые для ускорения процесса, следующие:

• если сумма текущего числа i равна 10, то мы знаем, что другого решения между i и i+8 нет. Например, после 27 следующее решение равно 36. Таким образом, мы можем сделать i += 9 вместо простого i++.
• если сумма больше 10, то мы не найдем решения, просто увеличивая первую цифру. Например, если i = 85, мы можем сразу перейти к 90, т.е. обнулить наименьшую цифру. Это выполняется с помощью i += (10 - i%10);
• если сумма меньше 10, например. 5, то вы можете напрямую добавить 5 вместо 1. Это выполняется с помощью i += (10 - total);

На практике можно было бы пойти дальше. Например, если i = 99000, то мы могли бы сразу прибавить 1000 вместо 10. Я так далеко не зашел, так как полученный код кажется уже немного надворным (0,15с вместо 1с).

#include <iostream>
#include <vector>

int sum(int d) {
    int ans = 0;
    while(d) {
        ans += d%10;
        d /= 10;
    }
    return ans;
}

int main() {
    int t;
    std::cin >> t;
    std::vector<int> mem(20001, 0);
    int kmax = 1;
    mem[1] = 19;
    while(t-- >0) {
        int i, k;
        std::cin >> k;
        int num = 1;
        if (k > kmax) {
            i = mem[kmax];
            num = kmax;
            while(true) {
                int total = sum(i);
                if(total == 10) {
                    mem[num] = i;
                    if (num == k) break;
                    num++;
                    i += 9;
                } else {
                    if (total > 10) {
                        i += (10 - i%10);
                    } else {
                        i += (10 - total);
                    }
                }
            }
            kmax = k;
        }
        std::cout << mem[k] <<"\n";
    }
    return 0;
}

Вот обязательная цифра динамической программы для полноты картины. Этот позволит вам найти 200 000-й (не говоря уже о 20 000-й) почти сразу с помощью бинарного поиска.

Код JavaScript:

function g(digits, i, sum, bound, memo){
  const key = String([i, sum, bound]);

  if (memo.hasOwnProperty(key))
    return memo[key];
    
  if (sum == 0)
    return memo[key] = 1;
    
  if (i == 0)
    return sum <= (bound ? digits[0] : 9);

  let result = 0;
  
  const k = bound ? digits[i] : 9;

  for (let d=0; d<=k && d<=sum; d++){
    const _bound = digits[i] == d ? bound : 0;
    result += g(digits, i-1, sum-d, _bound, memo);
  }
  
  return result;
}


function f(n, sum){
  const digits = [];
  
  while(n){
    digits.push(n % 10);
    n = Math.floor(n/10);
  }
  
  return g(digits, digits.length-1, sum, 1, {});
}

console.log(f(320002210, 10));

console.log(f(320002209, 10));

Вы можете решить эту проблему рекурсивным способом.

Если данное число начинается с цифры d, то сумма последующих цифр должна составлять 10-d. Поскольку числа не превышают 20000, они имеют не более 5 цифр, а первая — одна из 0, 1.

Простое решение — использовать четыре вложенных цикла. Затем вы проверяете, является ли последняя цифра законной.

n= 0
for d4= 0 to 1
    for d3= 0 to min(9, d-d4)
        for d2= 0 to min(9, d-d4-d3)
            for d1= 0 to min(9, d-d4-d3-d2)
                d0= 0 d-d4-d3-d2-d1
                if 0 <= d0 and d0 <= 9:
                    n+= 1
                    if n == k stop

Возможны некоторые микрооптимизации. Используя этот метод, я нахожу 502 различных решения.

Я неправильно истолковал ограничения, но, наконец, вот решение. ограничение 1‹=K‹=2*10^4 было для переменной K, значение числа X было положительным целым числом, поэтому я инициализировал x=1. Я применил оператор break (чтобы вывести его из выполнения, когда число будет найдено и напечатано) внутри бесконечного цикла, то есть while (1).

Включены следующие темы: рекурсия, итерации, операторы if, операторы управления циклом.

#include <bits/stdc++.h>

using namespace std;

int main()

{
  //write your code here

  //ios_base::sync_with_stdio(false);

 // cin.tie(NULL);

  int t;

  cin>>t;

  while(t>0)

  {

    int k;

    cin>>k;

    int x=1;

    while(1)

    {

     int sum=0;

     int d=x;

     while(d!=0)

     {

     sum+=d%10;

      d/=10;

     }

      if(sum==10)

      k--;

      if(k==0)

      {

      cout<<x<<"\n";

      break;

      }

      x++;

    }

    t--;

    }

     return 0;

     }