Числа с заданной суммой цифр

@pyton567 · Регистрация: 03.01.2024

Напишите программу, которая вычисляет количество чисел, состоящих из K цифр, для которых сумма цифр равна N .

Входные данные

Входная строка содержит два числа: количество цифр K и сумму цифр N , разделённых пробелами.

Выходные данные

Программа должна вывести одно число: количество чисел, состоящих из K цифр, для которых сумма цифр равна N .

Примеры
Входные данные
3 2
Выходные данные
6
Входные данные
3 30
Выходные данные
0
Мой код:

Python
1
2
3
4
5
6
7
8
k, n = map(int, input().split())
 
chh = 0
for i in range(int('1' + (k - 1) * '0'), int(k * '9') + 1):
    
    if n == sum(map(int, str(i))):
        chh += 1
print(chh)

Подскажите, как можно доработать код? В идеале задача должна решаться через рекурсию.

@isaak · 18.10.2025, 00:28

Исправил у ТС ошибку, теперь программа выводит нужные результат:

Python
1
2
3
4
5
6
7
8
k, n = map(int, input().split())
 
chh = 0
for i in range(int('1' + (k - 1) * '0'), int(k * '9') + 1):
 
    if n == sum(map(int, str(i))):
        chh += 2
print(chh)

@Gdez · 18.10.2025, 08:22

При к=7 время выполнения вылетает
И при к, n = 6, 6 неверный результат

@Catstail · 18.10.2025, 08:36

isaak, Вы можете объяснить, как работает это решение?

YuS_2 · 18.10.2025, 08:45

Не по теме:

Сообщение от SmallEvil

Но точные науки и программирование это не твоё.

Обрати свои советы к себе... не твое вообще, в принципе, раздавать советы, лучше займись самообразованием...

@Catstail · 18.10.2025, 09:00

Если незначащие нули в начале числа допустимы, то вот без особых затей:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
k, n = map(int, input().split())
if n>k*9:
    print(0)
elif n==k*9:
    print(1)
else:
    q=0
    v=[0]*k
    while True:
        if sum(v)==n:
            #print(v)  # если нужны разряды
            q+=1
        i=0
        while i<k:
            if v[i]<9:
                v[i]+=1
                break
            else:
                v[i]=0
                i+=1
        if (i < k):
            continue
        break
    print(q)

YuS_2 · 18.10.2025, 09:53

Сообщение от thyrex

Числа ведь могут быть и отрицательные

числа могут, конечно... цифры не могут.
Но это, кстати, почти заявка, на выполнение моего опрометчивого обещания, буде автор сей задачи если появится, упаду таки ему в ножки, посыплю голову пеплом и попрошу прощения.

- таки это шесть разных чисел

Да и ещё в условиях нет упоминания о том, что числа десятичные и целые, такшта при достаточно буйно развитой фантазии, можно тут наворотить таких решений, что автор задачи лопнет от счастья.

Добавлено через 7 минут

Сообщение от Catstail

Если незначащие нули в начале числа допустимы

Думаю в отношении питона, это вряд ли имелось в виду, здесь, скорее всего, на 100% прав thyrex

Сообщение от pyton567

как можно доработать код?

Python
1
2
3
4
5
6
7
8
k,n = map(int, input().split())
arr = list(range(-(1*10**k)+1,-(1*10**(k - 1))+1)) + list(range(1*10**(k-1),1*10**k))
chh = 0
for i in arr:
    if n == sum(map(int, str(abs(i)))):
        #print(i)
        chh += 1
print(chh)

@Catstail · 18.10.2025, 09:58

YuS_2, а почему Ваш код даёт верный результат? Из кода это совсем не очевидно...

YuS_2 · 18.10.2025, 10:03

Сообщение от Gdez

Сама задача:

Ну, а пока:
Уважаемый, Поляков-Еремин, прошу прощения, падаю в ножки и посыпаю голову пеплом!

Добавлено через 58 секунд

Сообщение от Catstail

Из кода это совсем не очевидно...

Почему не очевидно?
Вот же:

Сообщение от YuS_2

arr = list(range(-(1*10**k)+1,-(1*10**(k - 1))+1)) + list(range(1*10**(k-1),1*10**k))

массив отрицательных и положительных чисел...

Добавлено через 50 секунд
при желании, там можно распечатать сами числа...

@Catstail · 18.10.2025, 11:37

Сообщение от YuS_2

Почему не очевидно?
Вот же:

- и что? Почему это выражение равно верному результату?

А мое решение я могу объяснить:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
k, n = map(int, input().split())
if n>k*9:
    print(0)
elif n==k*9:
    print(1)
else:
    q=0       # здесь будет результат
    v=[0]*k # начальные значения разрядов
    while True:
        if sum(v)==n and v[0] != 0: # берём только раскладки с нужной суммой и без первого незначащего нуля
            #print(v)
            q+=1 # копим результат
        # блок получения следующего числа
        i=0   # номер увеличиваемого разряда       
        while i<k:  # пока не вышли за пределы v
            if v[i]<9:  # очередной разряд можно увеличить
                v[i]+=1 # увеличиваем
                break
            else:        # очередной разряд = 9 - сбрасываем в нуль
                v[i]=0
                i+=1    # и переходим к следующему разряду
        if (i < k): # если еще не вышли за пределы числа
            continue
        break
    print(q)

При к=7 n=20 у меня ответ 139068

Да, если могут быть и отрицательные числа, то результат нужно просто умножить на 2

YuS_2 · 18.10.2025, 12:02

Сообщение от Catstail

Почему это выражение равно верному результату?

потому, что это прямой перебор массива чисел с вычислением суммы цифр каждого числа и проверкой суммы на условие с инкрементированием счетчика... да, медленно, даже очень медленно и решение в лоб, но это какое-никакое, но правильное решение. Это, кстати, решение ТС-а, я просто добавил необходимый массив чисел.
Для увеличения скорости, то бишь, исключения прямого перебора потребуется динамическое программирование с заполнением таблицы (k + 1) x (n + 1) ... что-то типа:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?arr[i][j] = \sum_{d=0}^{9}arr[i-1][j-1]$
но, честно говоря, лень задумываться... если вдруг, кто-то заинтересуется, могу поподсказывать немного...

@SmallEvil · 18.10.2025, 13:00

Сообщение от YuS_2

Да и ещё в условиях нет упоминания о том, что числа десятичные и целые

Плюс ещё и поэтому задание является некорректным от а до я.
И решать его так же некорректно.

Но ты же набросился на красную тряпку и начал разглагольствовать о бесконечности про бесконечность.
И почему то набросился и на мой комментарий, который был как раз демонстрацией этой некорректности.
Но главное "быкануть" и доказывать своё слепое видение задачи)

@Catstail · 18.10.2025, 13:49

Сообщение от YuS_2

потому, что это прямой перебор массива

- Ваша правда!!! Не заметил в самом начале строки list!

YuS_2 · 18.10.2025, 14:06

Сообщение от Catstail

При к=7 n=20 у меня ответ 139068
Да, если могут быть и отрицательные числа, то результат нужно просто умножить на 2

По сути да, можно и *2

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def cntnum(k,n):
    def cntrec(x,s):
        if x == 0:
            return 1 if s == n else 0
        if s > n:
            return 0
        cnt = 0
        for d in range(10):
            cnt += cntrec(x-1, s+d)
        return cnt
    tcnt = 0
    for fd in range(1, 10):
        tcnt += cntrec(k-1, fd)
    return tcnt*2
 
a,b = map(int, input().split())
print(cntnum(a,b))

@Gdez · 18.10.2025, 14:50

Catstail,

При к=7 n=20 у меня ответ 139068

У автора - 174195

@Catstail · 18.10.2025, 15:05

Gdez, если брать дурацкие числа с незначащими нулями впереди, у меня получится столько же...

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
k, n = map(int, input().split())
if n>k*9:
    print(0)
elif n==k*9:
    print(1)
else:
    q=0
    v=[0]*k
    while True:
        if sum(v)==n: # and v[0] != 0:
            #print(v)
            q+=1
        i=0
        while i<k:
            if v[i]<9:
                v[i]+=1
                break
            else:
                v[i]=0
                i+=1
        if (i < k):
            continue
        break
    print(q)

@SmallEvil · 18.10.2025, 17:22

Таки задача для долбодятликов. С нулями впереди у них это числа такие, N-значные.

Логика у автора задачи вышла в окно, как и у некоторых участников этой темы.
Gdez, тебе отдельное спасибо за ссылку.
Говнокурсы

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <unordered_map>
 
 // Custom hash_combine function (inspired by Boost)
 template <class T>
 inline void hash_combine(std::size_t& seed, const T& v) {
     std::hash<T> hasher;
     seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
 }
 
 // Specialization of std::hash for std::pair
 template <typename S, typename T>
 struct PHash{
     inline size_t operator()(const std::pair<S, T>& val) const {
         size_t seed = 0;
         hash_combine(seed, val.first);
         hash_combine(seed, val.second);
         return seed;
     }
 };
 
std::unordered_map<std::pair<long long, long long>, long long, PHash<long long, long long>> mem_count;
 
long long f_R(long long d, long long sum){
   if (d == 0 || sum < 0)
      return 0;
   if (d == 1)
      return sum < 10;
   {
      auto m = mem_count.find({d, sum});
      if (m != mem_count.end())
         return m->second;
   }
   long long cnt{0}; 
   for(long long i = 0; i != 10; ++i)
      cnt += f_R(d-1, sum - i);
   mem_count.insert({{d, sum}, cnt});
   return cnt;
}
 
// использовать f для подсчета натуральных чисел без значащих нулей
// но это не по ТЗ, которое там что то себе подразумевает
long long f(long long d, long long sum){
   long long cnt{0};
   for(long long i = 1; i != 10; ++i)
      cnt += f_R(d-1, sum - i);
   return cnt;
}
 
int main(){
   long long digits{0}, dsum{0};
   std::cin >> digits >> dsum;
   std::cout << f_R(digits, dsum)<< std::endl;
}

@thyrex · 18.10.2025, 17:55

Сообщение от SmallEvil

С нулями впереди у них это числа такие, N-значные

за то как элегантно можно срезать на ЕГЭ с такой задачей

@SmallEvil · 18.10.2025, 18:04

Сообщение от thyrex

за то как элегантно можно срезать на ЕГЭ с такой задачей

Я всё это видел ещё в старших классах.
На областной олимпиаде по информатики(программирование).
Половину времени зовешь и ждешь инструкторов что бы пояснили задачу.
Это что то с чем то. И это у всех участников так было, а инструкторов 2-3 на всех (~50+/- участников).

Добавлено через 5 минут
Поправил функцию f для натуральных чисел и 0.

C++
1
2
3
4
5
6
7
8
long long f(long long d, long long sum){
   if (d == 1 && sum < 10)
      return 1;
   long long cnt{0};
   for(long long i = 1; i != 10; ++i)
      cnt += f_R(d-1, sum - i);
   return cnt;
}

Новые блоги и статьи Все статьи Все блоги /
23. что сделано за последнее время. anaschu 17.06.2026 • Эталон: Клиника НИИ питания РАМН, Москва — централизованный пищеблок, 225 коек, 180 пациентов • Git: репозиторий med2, ветка абсентеизм. Рабочий файл: СРесурсами1_v4. alp • Смежный проект:. . .	22. Подключение слоя системной динамики (потоковые диффуры): экономические метрики модели anaschu 17.06.2026 Апдейт модели: финансовый контур, разделение затрат Продолжаю развивать модель рабочего коллектива на AnyLogic. В этот раз работа шла над агентом Экономика — финансовым SD-слоем модели. Задача:. . .	[golang] Insert Delete GetRandom O(1) (Leetcode: 380) alhaos 16.06.2026 Insert Delete GetRandom O(1) Сложность: Medium Источник: LeetCode 380 Задача Реализовать структуру данных RandomizedSet, которая поддерживает следующие операции за O(1) в среднем:	Свет в конце тоннеля kumehtar 16.06.2026 Поймал себя на одной мысли. Раньше мне всегда казалось неправильным жить без чёткого понимания, куда всё идёт. Будто я иду по дороге судьбы, но не знаю, куда она ведёт. А раз не знаю — значит,. . .
[golang] Реализация стека с поддержкой получения минимального элемента за O(1) alhaos 16.06.2026 Min Stack Сложность: Medium Источник: LeetCode 155 Задача: Реализовать стек который поддерживает push, pop, top и получение минимального элемента за O(1). Методы:	[golang] Конкурентный fetcher с ограничением максимального количества одновременных HTTP запросов. alhaos 10.06.2026 Задача Реализовать конкурентный fetcher с ограничением максимального количества одновременных HTTP запросов. Сигнатура func Fetch(urls string, maxConcurrent int) Result Пример urls :=. . .	[golang] Состояние гонки (race condition) alhaos 10.06.2026 Состояние гонки (race condition) Состояние гонки (Race Condition) — это ошибка, возникающая при одновременном доступе нескольких горутин к одним и тем же данным без должной синхронизации. При этом. . .	Взрослые отношения, и почему они не получаются kumehtar 09.06.2026 Когда в детстве ребёнок не получает от родителей чего-то важного, он лишается не просто приятных переживаний, а основы для формирования определённых внутренних качеств и навыков. Если ребёнок не. . .

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,319
	18.10.2025, 08:22
	При к=7 время выполнения вылетает И при к, n = 6, 6 неверный результат 0

@Catstail Супер-модератор 38208 / 21141 / 4311 Регистрация: 12.02.2012 Сообщений: 34,753 Записей в блоге: 14
	18.10.2025, 08:36
	isaak, Вы можете объяснить, как работает это решение? 0

@Catstail Супер-модератор 38208 / 21141 / 4311 Регистрация: 12.02.2012 Сообщений: 34,753 Записей в блоге: 14
	18.10.2025, 09:58
	YuS_2, а почему Ваш код даёт верный результат? Из кода это совсем не очевидно... 0