0 / 0 / 0
Регистрация: 09.12.2018
Сообщений: 2
1

Распределение элементов по группам

09.12.2018, 03:11. Показов 1541. Ответов 1

Author24 — интернет-сервис помощи студентам
Возникла проблема в одной задаче, никак подход не могу найти:


Вася решил организовать турнир. Он получил n коробок с призами от спонсора. Каждая коробка содержит разные призы, но в каждой коробке призы одинаковые. Из накладной известно, что в i-й коробке содержится mi одинаковых призов. Васька решил наградить команду, которая победила. Команда может получить не меньше a призов, и не больше чем b призов. Теперь перед Василием встал вопрос: сколько дать призов команде-победителю и каких? Задача - подсчитать сколькими способами он может распределить призы.

Программа читает в одном рядке три целых числа: n, a и b, разделённые одним пропуском(1≤n≤10, 0≤a≤b≤10 000 000). Каждое из следующих n целых чисел такие, что i+3 число - это mi – количество конфет в i упаковке. (0≤mi≤1000000). Программа выводит на устройство стандартного вывода k mod 109+7.

Пример:
Ввод - 2 1 3 3 5
Вывод - 9

(Способы распределения: (1,0),(2,0),(3,0),(0,1),(0,2),(0,3),(1,1),(1,2),(2,1))

Я пробовал сначала находить для каждого отдельного количества упаковок количество всех возможных комбинаций и отсекать ненужные, но быстро понял, что это слишком затратно, особенно для больших чисел. Также нашёл одну формулу: Название: 3.jpg
Просмотров: 16

Размер: 4.3 Кб, но она подразумевает деление, что не подходит из-за того, что мне нужно выдать остаток от деления на 109+7, а также искать факториалы чисел до 109+7 тоже не очень удобно.

Возможно стоит с помощью какого-нибудь алгоритма перебрать все возможные варианты для каждого количества подарков, найти их остаток от деления на 109+7, и потом суммировать и выводить, но какого алгоритма?
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
09.12.2018, 03:11
Ответы с готовыми решениями:

Распределение по работников по группам
Помогите с задачей: В файле input.txt записаны сначала кол-во всех работников, далее по порядку...

Распределение элементов справочника по группам
Здраствуйте. Как можно изменить у существующего элемента справочника родителя, т.е. переместить...

Распределение студентов по группам
Всем привет. Столкнулся с проблемой, надо распределить студентов в базе данных на 3 группы....

Разделить множество элементов по группам с минимумом повторений
Всем доброго времени суток) помогите решить такою задачку, а именно: Есть n-количество вопросов и k...

1
0 / 0 / 0
Регистрация: 09.12.2018
Сообщений: 2
09.12.2018, 15:45  [ТС] 2
Цитата Сообщение от MonX94 Посмотреть сообщение
до 109+7
До 107

Добавлено через 50 секунд
Цитата Сообщение от MonX94 Посмотреть сообщение
mi
mi..
0
09.12.2018, 15:45
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
09.12.2018, 15:45
Помогаю со студенческими работами здесь

Скрытие элементов и добавление текста разным группам div по завершении анимации.
Доброго всем! Есть задача: 4 дива разделенные на 2 класса one и two надо: по щелчку на кнопке,...

Распределение элементов в <td>
Добрый вечер. Есть такая штука: &lt;table&gt; &lt;tr class=&quot;menu&quot; &gt; &lt;td height=30 valign=&quot;top&quot;...

Распределение элементов на форме
Вобщем проблема такая. Выставляю на форме элементы (кнопки, чекбоксы и т.д.) В свойствах формы...

Распределение расходов по видам деятельности для УСН в Бухгалтерии 2.0 (распределение зарплаты)
Добрый день. Бухгалтерия предприятия, редакция 2.0 (2.0.64.20). При закрытии месяца март 2015 г....


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru