Олимпиады по информатике (ХМАО - Югра)

   
 
Югорский НИИ ИТ, Югорский ФМЛ
Логин:   Пароль:    
 
   
 
Новости
О проекте
Регистрация
Гостевая книга
Форум
Архив задач
Состояние системы
Олимпиады
Работа в системе
Рейтинг
Новичкам
Методическое пособие
Дистанционное обучение
Дистрибутивы
Ссылки


Великий комбинатор

(Время: 1 сек. Память: 16 Мб Сложность: 60%)

Прежде всего в задаче надо определить количество имеющихся купюр, поделив X на 5. Обозначим Y=X/5. Теперь задача свелась к тому, чтобы разделить Y предметов между K+1 участниками дележа.

Мысленно разложим все купюры в ряд. Тогда каждое разбиение взаимно-однозначно соответствует расстановке между ними K перегородок: первому отдадим все, что до 1-й перегородки, второму - все между 1-й и 2-й и т.д.

А теперь представим, что сами перегородки тоже являются купюрами. Тогда ответ на поставленную задачу равен числу способов выбрать из Y+K купюр K, которые будут играть роль перегородок, т.е. CKY+K.

Заметим, что в ограничениях задачи вычисления не умещаются ни в один из стандартных типов. Поэтому надо использовать длинную арифметику.

[Все попытки] [Задача]


 
     
Югорский НИИ ИТ, Югорский ФМЛ