Задача 401 с acmp

Новичок · Регистрация: 17.07.2012

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

Всем привет. Есть такая задача из категории "Динамическое программирование". В динамике я всегда слаб. Но возможно тут как-то и комбинаторикой можно решить. Буду очень рад если кто-то подскажет идею решения(все решение не обязательно)

У вас имеется N выстроенных в ряд коробок, A красных и B синих шаров. Все красные шары (аналогично и синие) идентичны. Вы можете класть шары в коробки. Разрешается размещать в коробках шары как одного, так и двух видов одновременно. Так же разрешается оставлять некоторые из коробок пустыми. Не обязательно класть все шары в коробки.

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

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

Входной файл INPUT.TXT содержит целые числа N, A, B. (1 <= N <= 20, 0 <= A, B <= 20)

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

В выходной файл OUTPUT.TXT выведите ответ на задачу.

@Dani · 09.07.2017, 00:47

Нужно найти число разбиений x красных шаров на n коробок и число разбиений y синих на n коробок. Потом их перемножить.
Как найти число разбиений каких-то шаров на коробки: чтобы разбить шары на коробки, будем ставить перегородки между ними. Число шаров между перегородками с номерами k и k + 1 будет показывать число шаров в k + 1ой урне (все нумеруем с единицы). Исключения для первой и последней перегородок: число шаров до первой перегородки показывает число шаров в 1ой урне, число шаров после последней перегородки показывает число шаров, которые мы не положили в коробки (т.к. по условию не все шары обязательно ложить).
Пример: o o| o o|| o, будет показывать, что в урнах с номерами

2 шара
2 шара
0 шаров

и 1 шар остался на руках.
Как найти число расстановок перегородок? Для подсчета используем число сочетаний с повторениями: $https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{(a + b - 1)!}{b! (a - 1)!}$ (число сочетаний с повторениями из a по b). Нам же нужно расставитьk перегородок, позиция которых - число от 0 до n включительно (т.е. всего (n + 1) возможное значение), где n - число шаров.
Подставляем в формулу n + 1 вместо a и k вместо b
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{(n + k)!}{k! n!}$
Пример:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?n = 2$
$https://www.cyberforum.ru/cgi-bin/latex.cgi?x = 1$
$https://www.cyberforum.ru/cgi-bin/latex.cgi?y = 1$
$https://www.cyberforum.ru/cgi-bin/latex.cgi?ANSWER = \frac{(n + x)!}{x! n!} * \frac{(n + y)!}{y! n!} = \frac{3!}{1! 2!} * \frac{3!}{1! 2!} = 9$

Новичок 1642 / 1091 / 487 Регистрация: 17.07.2012 Сообщений: 5,345
		1
	Задача 401 с acmp 08.07.2017, 21:09. Показов 4884. Ответов 1 Метки нет (Все метки) Всем привет. Есть такая задача из категории "Динамическое программирование". В динамике я всегда слаб. Но возможно тут как-то и комбинаторикой можно решить. Буду очень рад если кто-то подскажет идею решения(все решение не обязательно) У вас имеется N выстроенных в ряд коробок, A красных и B синих шаров. Все красные шары (аналогично и синие) идентичны. Вы можете класть шары в коробки. Разрешается размещать в коробках шары как одного, так и двух видов одновременно. Так же разрешается оставлять некоторые из коробок пустыми. Не обязательно класть все шары в коробки. Требуется написать программу, которая определяет количество различных способов, которыми возможно заполнить коробки шарами. Входные данные Входной файл INPUT.TXT содержит целые числа N, A, B. (1 <= N <= 20, 0 <= A, B <= 20) Выходные данные В выходной файл OUTPUT.TXT выведите ответ на задачу. 0

@Dani 1405 / 647 / 135 Регистрация: 11.08.2011 Сообщений: 2,299 Записей в блоге: 2
	09.07.2017, 00:47	2
	Сообщение было отмечено Новичок как решение Решение Нужно найти число разбиений `x` красных шаров на `n` коробок и число разбиений `y` синих на `n` коробок. Потом их перемножить. Как найти число разбиений каких-то шаров на коробки: чтобы разбить шары на коробки, будем ставить перегородки между ними. Число шаров между перегородками с номерами `k` и `k + 1` будет показывать число шаров в `k + 1`ой урне (все нумеруем с единицы). Исключения для первой и последней перегородок: число шаров до первой перегородки показывает число шаров в 1ой урне, число шаров после последней перегородки показывает число шаров, которые мы не положили в коробки (т.к. по условию не все шары обязательно ложить). Пример: o o\| o o\|\| o, будет показывать, что в урнах с номерами 2 шара 2 шара 0 шаров и 1 шар остался на руках. Как найти число расстановок перегородок? Для подсчета используем число сочетаний с повторениями: $https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{(a + b - 1)!}{b! (a - 1)!}$ (число сочетаний с повторениями из a по b). Нам же нужно расставить`k` перегородок, позиция которых - число от 0 до n включительно (т.е. всего (n + 1) возможное значение), где `n` - число шаров. Подставляем в формулу `n + 1` вместо `a` и `k` вместо `b` $https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{(n + k)!}{k! n!}$ Пример: $https://www.cyberforum.ru/cgi-bin/latex.cgi?n = 2$ $https://www.cyberforum.ru/cgi-bin/latex.cgi?x = 1$ $https://www.cyberforum.ru/cgi-bin/latex.cgi?y = 1$ $https://www.cyberforum.ru/cgi-bin/latex.cgi?ANSWER = \frac{(n + x)!}{x! n!} * \frac{(n + y)!}{y! n!} = \frac{3!}{1! 2!} * \frac{3!}{1! 2!} = 9$ 1

Задача 401 с acmp

Решение