В аудитории есть n студентов, которые работают над групповыми проектами. Студенты будут разделены на группы (группа может состоять и из одного студента), после чего каждый студент в группе будет работать над своей независимой частью проекта, а затем они объединят результаты в рамках этой группы. Известно, что i-й студент выполнит свою работу ровно за ai минут.
Если студенты в группе работают с разной скоростью, то это раздражает как тех, кто делает свою работу быстро и ждёт остальных, так и тех, кто делает её медленно и задерживает всю группу. Несбалансированностью группы называется разница между максимальным ai в группе и минимальным ai в группе. Обратите внимание, что несбалансированность группы из одного студента равна 0. Сколькими способами можно разбить студентов на группы так, чтобы суммарная несбалансированность всех групп не превосходила k?
Два разбиения считаются различными, если какие-то два студента были в одной группе в одном разбиении, но оказались в разных группах в другом разбиении.
Примечание
В первом примере возможны три разбиения:
- Первый и второй студенты образуют одну группу, а третий студент — другую. Итоговая несбалансированность равняется 2 + 0 = 2.
- Первый студент будет в группе один, а второй и третий студенты образуют другую группу. Несбалансированность равняется 0 + 1 = 1.
- Все три студента будут в разных группах. Несбалансированность будет равна 0.
В третьем примере суммарная несбалансированность должна быть равна 0, поэтому каждый студент должен работать индивидуально.