|
||||||||||||||
МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике
Дистанционные семинары
по подготовке к олимпиадам по информатике
Задача 15-3. Великий Комбинатор
(Разбор)
Прежде всего в задаче надо определить количество имеющихся купюр, поделив X на 5. Обозначим Y=X/5. Теперь задача свелась к тому, чтобы разделить Y предметов между K+1 участниками дележа.
Мысленно разложим все купюры в ряд. Тогда каждое разбиение взаимнооднозначно соответствует расстановке между ними K перегородок: первому отдадим все, что до 1-й перегородки, второму - все между 1-й и 2-й и т.д.
А теперь представим, что сами перегородки тоже являются купюрами. Тогда ответ на поставленную задачу равен числу способов выбрать из Y+K купюр K, которые будут играть роль перегородок, т.е. CY+KK.
Заметим, что в ограничениях задачи вычисления не умещаются ни в один из стандартных типов. Поэтому надо использовать длинную арифметику.