919B | n-е числа, имеющие di git sum как 10 | Codeforces

Question

Вот ссылка на вопрос . По сути, он просит найти число kth с суммой di git равным 10. Я пробовал несколько решений, а также искал решения в Интернете. В частности это один (также разделены ниже). Тот, кто имеет постоянное время, говорит о выбросах в Arithmeti c Progression и использует его, чтобы найти число nth, имеющее сумму 10. Очевидно, что код неверен, так как он не подходит для тестовых случаев, когда k=1000 et c.

#include <bits/stdc++.h> 

using namespace std; 

int findNth(int n) 
{ 
    int nthElement = 19 + (n - 1) * 9; 
    int outliersCount = (int)log10(nthElement) - 1; 

    // find the nth perfect number 
    nthElement += 9 * outliersCount; 
    return nthElement; 
} 

int main() 
{ 
    cout << findNth(5) << endl; 
    return 0; 
} 

В конце концов я закончил тем, что написал комбинацию Арифмети c Прогрессия + грубая сила, как показано ниже

#include <bits/stdc++.h>
using namespace std;
#define ll unsigned long long


int main() {
    int n;
    cin >> n;

    int count = 0;
    ll i = 19;
    for (; ; i += 9) {
        int curr = i;
        int localSum = 0;

        while (curr) {
            localSum += curr%10;
            curr /= 10;
        }

        if (localSum == 10) {
            count += 1;
        }

        if (count == n) {
            break;
        } 
    }
    cout << i << endl;
    return 0;
}

Мне интересно, нет ли постоянного времени или лучшего алгоритма, который не требует, чтобы я вычислял сумму, но мой алгоритм всегда скачет так, что у меня есть число, чье значение di git равно 10?

Answer 1

Вот решение Python, которое вы можете перевести на C ++.

cached_count_ds_l = {}
def count_digit_sum_length (s, l):
    k = (s, l)
    if k not in cached_count_ds_l:
        if l < 2:
            if s == 0:
                return 1
            elif l == 1 and s < 10:
                return 1
            else:
                return 0
        else:
            ans = 0
            for i in range(min(10, s+1)):
                ans += count_digit_sum_length(s-i, l-1)
            cached_count_ds_l[k] = ans
    return cached_count_ds_l[k]

def nth_of_sum (s, n):
    l = 0
    while count_digit_sum_length(s, l) < n:
        l += 1
    digits = []

    while 0 < l:
        for i in range(10):
            if count_digit_sum_length(s-i, l-1) < n:
                n -= count_digit_sum_length(s-i, l-1)
            else:
                digits.append(str(i))
                s -= i
                l -= 1
                break
    return int("".join(digits))

print(nth_of_sum(10, 1000))

Идея состоит в том, чтобы использовать динамическое c программирование, чтобы найти число чисел заданной максимальной длины с учитывая ди git сум. И затем использовать это, чтобы вычеркнуть целые блоки чисел на пути к поиску правильного.

Основной лог c выглядит так:

0 numbers of length 0 sum to 10
  - need longer
0 numbers of length 1 sum to 10
  - need longer
9 numbers of length 2 sum to 10
  - need longer
63 numbers of length 3 sum to 10
  - need longer
282 numbers of length 4 sum to 10
  - need longer
996 numbers of length 5 sum to 10
  - need longer
2997 numbers of length 6 sum to 10
  - answer has length 6

Looking for 1000th number of length 6 that sums to 10
  - 996 with a leading 0 sum to 10
    - Need the 4th past 99999
  - 715 with a leading 1 sum to 10
    - Have a leading 1
Looking for 4th number of length 5 that sums to 9
  - 495 with a leading 0 sum to 9
    - Have a leading 10
Looking for 4th number of length 4 that sums to 9
  - 220 with a leading 0 sum to 9
    - Have a leading 100
Looking for 4th number of length 3 that sums to 9
  - 55 with a leading 0 sum to 9
    - Have a leading 1000
Looking for 4th number of length 2 that sums to 9
  - 1 with a leading 0 sum to 9
    - Need the 3rd past 9
  - 1 with a leading 1 sum to 9
    - Need the 2nd past 19
  - 1 with a leading 2 sum to 9
    - Need the 1st past 29
  - 1 with a leading 3 sum to 9
    - Have a leading 10003

Поиск 1-го числа длины 1, которая суммирует до 6 - 0 с ведущей от 0 до 6 - нужна 1-я после 0 - 0 с ведущей от 1 до 6 - нужна 1-я после 1 - 0 с ведущей от 2 до 6 - нужна 1-я последние 2 - 0 с ведущей суммой от 3 до 6 - нужно 1-е прошедшее 3 - 0 с ведущей 4 от суммы до 6 - нужно 1-е прошедшее 4 - 0 с ведущей от 5 до 6 - нужно 1-е прошедшее 5 - 1 с ведущая сумма от 6 до 6 - имеет ведущую 100036

И она заканчивается за доли секунды.

Кстати, миллионная часть - это 20111220000010, миллиардная - это 10111000000002000000010000002100, а триллионная - 10000000100000100000100000000000001000000000000100000000010110001000.