Ограничение по памяти: 256 мегабайт Галымжан и наш старый друг Алиса решили провести олимпиаду для студентов, в которой будет участвовать n команд по k человек в каждой. Для проведения соревнований университет вы- дал Алисе и Галымжану 3 вида призов каждого по a, b, c штук соответственно. Сейчас Алиса и Галым должны отдохнуть после тяжелых экзаменов и просят вас определить максимальное количе- ство команд, которым они дадут призы. Алиса всегда борется за справедливость и не хочет чтобы участн

Для решения этой задачи мы можем использовать подход динамического программирования.

1. Создадим таблицу размером (n+1) x (k+1) x 3, где n – количество команд, k – количество участников в каждой команде, 3 – количество призовых видов. Инициализируем ее нулями.

2. Заполним таблицу с помощью циклов. Для каждого возможного значения i (от 0 до n) и j (от 0 до k) проходимся по всем призовым видам.

3. Для каждой ячейки таблицы, кроме первой строки и первого столбца, рассчитываем максимальное количество команд, которым можно дать приз. Это будет максимум из трех возможных вариантов:
– Если текущее количество участников j в команде равно 0, то максимальное количество команд, которым можно дать приз, равно значению ячейки в предыдущем столбце.
– Если количество участников j в команде больше 0, то максимальное количество команд, которым можно дать приз, равно максимуму из трех значений:
– Значение ячейки в предыдущем столбце, если текущий призовый вид не выбран для команды с j участниками.
– Значение ячейки в текущей строке и предыдущем столбце минус k, если текущий призовый вид выбран для команды с j участниками.
– Значение ячейки в предыдущей строке и текущем столбце, если текущий призовый вид выбран для команд с j участниками.

4. В конце проходимся по всем возможным значениям в таблице и выбираем максимальное количество команд, которым можно дать приз.

5. Возвращаем полученный результат.

Асимптотическая сложность этого алгоритма составляет O(n*k).