Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
MonX94
0 / 0 / 0
Регистрация: 09.12.2018
Сообщений: 2
1

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

09.12.2018, 03:11. Просмотров 338. Ответов 1

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


Вася решил организовать турнир. Он получил 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
Просмотров: 10

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

Возможно стоит с помощью какого-нибудь алгоритма перебрать все возможные варианты для каждого количества подарков, найти их остаток от деления на 109+7, и потом суммировать и выводить, но какого алгоритма?
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.12.2018, 03:11
Ответы с готовыми решениями:

Распределение элементов вектора внизу бинарного дерева
Здравствуйте У меня такое задание : Дан вектор неопределенной длины (числа). Нужно сделать...

Двусвязный список, распределение элементов при вставке
Сам список и функция добавления: #include<iostream> #include<string> #include <fstream> ...

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

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

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

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

Добавлено через 50 секунд
Цитата Сообщение от MonX94 Посмотреть сообщение
mi
mi..
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
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
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru