Бочки

@roman20 · Регистрация: 17.11.2021

Студворк — интернет-сервис помощи студентам

На берегу большого озера стоит бочка объемом N литров и набор K бочек с объемами 1л, 2л, 3л, …, K литров. Ваню заинтересовал такой вопрос: сколькими способами можно заполнить бочку объемом N литров, используя набор из K бочек. (переливать бочку нельзя, в бочке, из которой выливают воду, воды не должно оставаться). Помогите решить его задачу.

Входные данные
В единственной строке входного файла записаны два натуральных числа. N(0<N<100) – емкость бочки, которую нужно заполнить водой. K (0<K<100) – количество бочек в наборе от 1л до Kл.

Исходные данные
В единственной строке вывести одно число – количество способов, которыми можно заполнить бочку.

Входные данные Выходные данные
input.txt output.txt
3 3 4
2 5 2
5 2 8

@iSmokeJC · 10.12.2022, 13:28

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

Входные данные Выходные данные
input.txt output.txt
3 3 4
2 5 2
5 2 8

Вот что тут в input.txt, а что в output.txt?
Скопипастил и ладно, там разберутся, да?

@Red white socks · 10.12.2022, 15:07

Сколькими способами можно заполнить бочку объемом N литров

@roman20 · 10.12.2022, 16:40 **[ТС]**

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

Вот что тут в input.txt, а что в output.txt?
Скопипастил и ладно, там разберутся, да?

Извините не заметил
Входные данные
input.txt
3 3
2 5
5 2
Выходные данные
output.txt
4
2
8

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

Сообщение от Red white socks

Сколькими способами можно заполнить бочку объемом N литров

Спасибо! Но почему-то она не проходит

@Red white socks · 10.12.2022, 16:53

roman20, так, к слову, я очень редко выкладываю решения под ключ. Только содержательную часть. Чтобы вместо копипаста у вас хоть одна извилина да поработала бы.

@roman20 · 12.12.2022, 22:36 **[ТС]**

Что может быть не так с кодом? Задача работает но полностью не проходит (((

Python
1
2
3
4
5
6
7
8
9
10
11
12
def magic(n,k):
    if n<0:
        return 0
    elif n==0:
        return 1
    else:
       return sum(magic((n-i),k) for i in range(1, k+1))
    
 
n,k=input().split()
n,k=int(n),int(k)
print(magic(n,k))

@Red white socks · 13.12.2022, 08:31

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

Что может быть не так с кодом?

Могу сразу сказать - отступов нет. Дальше не смотрел.

@roman20 · 13.12.2022, 08:45 **[ТС]**

Сообщение от Red white socks

Могу сразу сказать - отступов нет. Дальше не смотрел.

Отступы сделал

Python
1
2
3
4
5
6
7
8
9
10
11
12
def magic(n,k):
    if n<0:
        return 0
    elif n==0:
        return 1
    else:
       return sum(magic((n-i),k) for i in range(1, k+1))
    
 
n,k=input().split()
n,k=int(n),int(k)
print(magic(n,k))

@Red white socks · 13.12.2022, 09:03

С этим кодом всё так, потому что это мой код: Сколькими способами можно заполнить бочку объемом N литров
Но для больших n он будет работать медленно, ибо - рекурсия.
Лучший способ - использовать динамическое программирование.
Кэширование также может вылечить проблему (до определенного момента)

Новые блоги и статьи Все статьи Все блоги /
AkelPad-скрипты, структуры, и немного лирики.. testuser2 05.04.2026 Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .	Отображение реквизитов в документе по условию и контроль их заполнения Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеСпецтехники", разработанного в конфигурации КА2. Данный документ берёт данные из другого нетипового документа. . .	Фото всей Земли с борта корабля Orion миссии Artemis II kumehtar 04.04.2026 Это первое подобное фото сделанное человеком за 50 лет. Снимок называют новым вариантом легендарной фотографии «The Blue Marble» 1972 года, сделанной с борта корабля «Аполлон-17». Новое фото. . .	Вывод диалогового окна перед закрытием, если документ не проведён Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать программный контроль на предмет проведения документа. . .
Программный контроль заполнения реквизита табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: 1. Реализовать контроль заполнения реквизита. . .	wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/	Программная установка даты и запрет ее изменения Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .	Вывод данных в справочнике через динамический список Maks 01.04.2026 Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .

@roman20 0 / 0 / 0 Регистрация: 17.11.2021 Сообщений: 38

	Бочки 10.12.2022, 00:03. Показов 1236. Ответов 8 Метки нет (Все метки) На берегу большого озера стоит бочка объемом N литров и набор K бочек с объемами 1л, 2л, 3л, …, K литров. Ваню заинтересовал такой вопрос: сколькими способами можно заполнить бочку объемом N литров, используя набор из K бочек. (переливать бочку нельзя, в бочке, из которой выливают воду, воды не должно оставаться). Помогите решить его задачу. Входные данные В единственной строке входного файла записаны два натуральных числа. N(0<N<100) – емкость бочки, которую нужно заполнить водой. K (0<K<100) – количество бочек в наборе от 1л до Kл. Исходные данные В единственной строке вывести одно число – количество способов, которыми можно заполнить бочку. Входные данные Выходные данные input.txt output.txt 3 3 4 2 5 2 5 2 8 0

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	10.12.2022, 15:07
	Сколькими способами можно заполнить бочку объемом N литров 0

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	10.12.2022, 16:53
	roman20, так, к слову, я очень редко выкладываю решения под ключ. Только содержательную часть. Чтобы вместо копипаста у вас хоть одна извилина да поработала бы. 2

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	13.12.2022, 09:03
	С этим кодом всё так, потому что это мой код: Сколькими способами можно заполнить бочку объемом N литров Но для больших n он будет работать медленно, ибо - рекурсия. Лучший способ - использовать динамическое программирование. Кэширование также может вылечить проблему (до определенного момента) 1