Задача №1972. Первый ход
Дима и Катя играют в следующую игру: каждому игроку дается набор из N карточек, на которых написаны натуральные числа от 1 до N включительно. Ходы делаются одновременно. За один ход каждый игрок выбирает какую-то карточку, которую он будет использовать (естественно, не сообщая об этом сопернику). Выбранные игроками карточки открываются, и сумма выигрыша (или проигрыша) каждого определяется по специальной таблице, которая известна игрокам заранее. Карточки, которые были использованы в предыдущих ходах, в игру не возвращаются.
Пример таблицы для N=4 показан на рисунке: в первом столбце перечислены возможные ходы Димы, в первой строке – возможные ходы Кати. На пересечении строки и столба записана сумма выигрыша Димы (если число положительное) или сумма его проигрыша (если число отрицательное).
| 1 | 2 | 3 | 4 |
| 1 | 5 | 0 | 1 | -9 |
| 2 | -2 | -4 | 8 | -6 |
| 3 | 9 | -10 | 6 | 3 |
| 4 | 5 | 1 | -1 | -3 |
Определите оптимальный первый ход для Димы (указание: используйте маскиминный критерий).
Сначала вводится число N (натуральное, не превосходит 20), затем вводится N строк по N чисел в каждой – таблица сумм выигрышей. Числа в таблице целые, по модулю не превосходят 1000.
Выведите единственное число – оптимальный первый ход Димы. В случае, если оптимальных ходов несколько – выведите тот, где используется карточка с наибольшим номером.
2 4 -8 -1 2
2