0409. Сразимся?

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

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

  • В игре есть ровно три вида существ: Огнедышащие голуби, Зелёные злые обои и Коленчатые пингвины.
  • В начале игры игроки договариваются и оставляют в игре N первых видов существ. Остальные виды в игре не участвуют.
  • Для каждого вида i устанавливается лимит на максимальное количество существ этого вида – Li.
  • Игрокам разадется стартовый набор существ.
  • Фиксируется стоимость продажи одного существа вида iCi.
  • Для всех пар i, j фиксируется число Ai,j сколько существ вида j может убить одно существо вида i.
  • Начинается игра. Игроки по очереди делают ходы.
  • Игра длится T ходов.
  • Выигрыш игрока – стоимость всех его существ, имеющихся у него в конче игры.
В свой ход игрок может:
  1. Получить одно существо какого-либо типа.
  2. Напасть всеми своими существами одного вида на всех существ одного вида противника.
  3. Ничего не делать. Ход при этом тратится.
Бой проходит следующим образом:
  • Пусть атакующие существа вида i и их x, а атакованные существа вида j и их y.
  • Атакующие существа убивают некоторое количество атакованных существ. Количество погибших считается минимум из y и x *Ai,j.
  • Выжившие существа наносят ответный удар по таким же правилам.

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

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

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

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

В первой строке содержится два числа N – количество оставленных видов существ и T – количество ходов в игре. 1 ≤ N ≤ 3, 1 ≤ T ≤ 50. Следующая строка содержит N числел Li – ограничение количества существ для всех видов. 0 ≤ Li ≤ 4. Следующие N строк содержат по N чисел Ai,j – сколько существ вида j может убить одно существо вида i. 0 ≤ Ai,j ≤ 1024. Следующая строка содержит N числел Ci – стоимость продажи существ для вида i. 0 ≤ Ci ≤ 106. Следующие две строки содержат по N чисел Cnti – стартовые количества существ вида i у игроков. 0 ≤ Cnti ≤ Li.

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

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

Пример:

battle.inbattle.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 года

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



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