Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1055. Игра
Обход дерева игры, α-β процедураОлимпиадные задачи на русском языке
| 15/10/2005 | Личное первенство Южного Урала (6) |
| 29/04/2013 | Занятие 26 (D) |
Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Макси и Мини играют в следующую игру. Квадратный лист бумаги разделяется линиями на `N\ times\ N` клеток,
и в каждой клетке записывается целое число от –100 до 100. Игроки ходят по очереди.
Каждый игрок может либо взять себе весь оставшийся прямоугольник, либо разрезать его по вертикальной или
горизонтальной линии на два прямоугольника и взять себе любую из частей.
Игра заканчивается, когда игрок при очередном ходе забирает себе всю оставшуюся фигуру.
По окончании игры подсчитывается сумма чисел на взятых игроками частях. Побеждает тот игрок, у которого сумма больше.
Напишите программу, которая по значениям в клетках в начале игры определит
максимальный перевес первого игрока над вторым, если оба играют максимально прибыльно для себя.
В первой строке входного файла содежится число `T` (`0\ <\ T\ ≤\ 10`) – количество тестов в файле.
Каждый тест состоит из набора строк. В первой строке содержится целое число `N` (`0\ <\ N\ ≤\ 10`) – размер поля,
затем следует `N` строк, в каждой содержится `N` целых чисел `A_{ij}` (`-100\ ≤\ A_{ij}\ ≤\ 100`), разделенных
пробелами – числа, записанные в соответствующих клетках.
Для каждого теста вывести на соответствующей строке максимальный перевес первого игрока над вторым по окончании игры,
если оба играют максимально прибыльно для себя.
Пример ввода
2 3 1 1 1 1 1 1 1 1 1 2 -10 1 1 1
Пример вывода
9 -7
