0409. Сразимся?

Имя входного файла:	battle.in
Имя выходного файла:	battle.out
Ограничение по времени:	2 s
Ограничение по памяти:	256 megabytes

Валентин и Богдан играют в одну очень странную игру. Игра заключается в следующем:

• В игре есть ровно три вида существ: Огнедышащие голуби, Зелёные злые обои и Коленчатые пингвины.
• В начале игры игроки договариваются и оставляют в игре N первых видов существ. Остальные виды в игре не участвуют.
• Для каждого вида i устанавливается лимит на максимальное количество существ этого вида – L_i.
• Игрокам разадется стартовый набор существ.
• Фиксируется стоимость продажи одного существа вида i – C_i.
• Для всех пар i, j фиксируется число A_i,j сколько существ вида j может убить одно существо вида i.
• Начинается игра. Игроки по очереди делают ходы.
• Игра длится T ходов.
• Выигрыш игрока – стоимость всех его существ, имеющихся у него в конче игры.

В свой ход игрок может:

1. Получить одно существо какого-либо типа.
2. Напасть всеми своими существами одного вида на всех существ одного вида противника.
3. Ничего не делать. Ход при этом тратится.

Бой проходит следующим образом:

• Пусть атакующие существа вида i и их x, а атакованные существа вида j и их y.
• Атакующие существа убивают некоторое количество атакованных существ. Количество погибших считается минимум из y и x *A_i,j.
• Выжившие существа наносят ответный удар по таким же правилам.

Поскольку деньги игроков интересуют меньше, чем азарт, то в первую очередь они хотят максимизировать следующую величину: свой выигрыш минус выигрыш соперника. Во вторую очередь игроки стремятся максимизировать свой выигрыш.

Валентин и Богдан профессионалы и играют всегда оптимально. Вам известны все установленные ограничения и стартовые наборы существ.

Вычислите выигрыши Валентина и Богдана и первый ход первого игрока при оптимальной игре обоих. Валентин ходит первым.

Формат входного файла

В первой строке содержится два числа N – количество оставленных видов существ и T – количество ходов в игре. 1 ≤ N ≤ 3, 1 ≤ T ≤ 50. Следующая строка содержит N числел L_i – ограничение количества существ для всех видов. 0 ≤ L_i ≤ 4. Следующие N строк содержат по N чисел A_i,j – сколько существ вида j может убить одно существо вида i. 0 ≤ A_i,j ≤ 1024. Следующая строка содержит N числел C_i – стоимость продажи существ для вида i. 0 ≤ C_i ≤ 10⁶. Следующие две строки содержат по N чисел Cnt_i – стартовые количества существ вида i у игроков. 0 ≤ Cnt_i ≤ L_i.

Формат выходного файла

В первой строке выведите выигрыши первого и второго игроков. Во второй строке выведите тип первого хода. Если это первый тип, то выведите номер вида, который был получен. Если это второй тип, то выведите два числа: тип атакующих существ и тип атакованных существ. Если это третий тип, то больше ничего выводить не требуется. Если оптимальных первых ходов несколько, то вывести любой из них.

Пример:

battle.in	battle.out
1 1 2 3 5 1 1	10 5 1 1
2 3 1 2 1 1 1 1 4 4 0 0 0 0	8 4 1 1
2 3 1 2 0 0 0 0 4 4 1 1 1 1	12 12 3

Источник: Чемпионат ПетрГУ по программированию. 1 марта 2015 года

Обсудить       Отправить решение



Версия для печати