1. Идея

Нужно перебрать все числа от 1 до n, для каждого посчитать сумму его цифр и проверить, равна ли она s.

Если равна — увеличиваем ответ.

Такой подход подходит по ограничениям: n <= 10^6, а сумма цифр одного числа считается очень быстро.

2. Наблюдения

1. Сумма цифр числа считается независимо от других чисел.
2. Чтобы найти сумму цифр числа, можно:
   • брать последнюю цифру через x % 10,
   • добавлять её к сумме,
   • убирать последнюю цифру через x //= 10 или x /= 10.
3. Так как n не больше миллиона, у каждого числа не больше 7 цифр. Значит, проверка одного числа занимает совсем немного операций.
4. Максимальная возможная сумма цифр при таких ограничениях невелика, но в этой задаче это не даёт более простого решения в рамках предложенного эталона — всё равно достаточно обычного перебора.

Например, для числа 203:

• 203 % 10 = 3, сумма 3
• 20 % 10 = 0, сумма 3
• 2 % 10 = 2, сумма 5

Значит, сумма цифр числа 203 равна 5.

3. Алгоритм

1. Считываем n и s.
2. Заводим переменную ans = 0.
3. Для каждого числа i от 1 до n:
   • считаем сумму его цифр;
   • если она равна s, увеличиваем ans.
4. Выводим ans.

4. Почему это работает

Мы рассматриваем все числа от 1 до n без пропусков.

Для каждого числа алгоритм точно вычисляет сумму его цифр:

• последовательно берёт все цифры справа налево,
• складывает их,
• после удаления всех цифр получает полную сумму цифр числа.

После этого:

• если сумма цифр равна s, число должно быть учтено в ответе;
• если не равна, число не должно быть учтено.

Так как каждое число проверяется ровно один раз, а подходящих чисел мы прибавляем ровно по одному, итоговое значение ans и есть количество чисел от 1 до n с суммой цифр s.

5. Сложность

Пусть у числа не более k цифр. Тогда сумма цифр одного числа считается за O(k).

Мы проверяем n чисел, поэтому общая сложность:

• O(n * k)

Так как n <= 10^6, а k мало, этого достаточно.

Память:

• O(1), потому что используются только несколько переменных.

6. Код на C++17

#include <iostream>
using namespace std;

int digit_sum(int x) {
    int sum = 0;
    while (x > 0) {
        sum += x % 10;
        x /= 10;
    }
    return sum;
}

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

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (digit_sum(i) == s) {
            ans++;
        }
    }

    cout << ans << '\n';
    return 0;
}

7. Код на Python 3

n, s = map(int, input().split())

ans = 0

for i in range(1, n + 1):
    x = i
    digit_sum = 0
    while x > 0:
        digit_sum += x % 10
        x //= 10
    if digit_sum == s:
        ans += 1

print(ans)