Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Теория игр

(Время: 1 сек. Память: 16 Мб Сложность: 28%)

Одним из интересных объектов, изучаемых в теории игр, являются так называемые антагонистические игры двух лиц. Такие игры характеризуются множеством X стратегий первого игрока, множеством Y стратегий второго игрока и функцией выигрыша K(x, y) (x из X, y из Y). Если множества стратегий X и Y конечны, то такую игру принято называть матричной, так как функцию выигрыша K в этом случае удобно задавать матрицей.

Рассмотрим матричную игру, в которой X = {1,…,n}, Y = {1,…,m}. Матрицу выигрышей обозначим символом K. Нижним значением игры назовем число maxi=1..nminj=1..m Kij . Верхним значением игры назовем число minj=1..mmaxi=1..n Kij. Отметим также, что игры, у которых нижнее и верхнее значение совпадают, называются играми с седловой точкой.

Задана матрица выигрышей K для некоторой матричной игры. Найдите ее верхнее и нижнее значение.

Входные данные

Первая строка входного файла INPUT.TXT содержит целые числа n и m (1 ≤ n,m ≤ 100). Далее следуют n строк по m чисел в каждой. j-ое число i-ой строки равно Kij . Все Kij по модулю не превосходят 1000.

Выходные данные

В выходной файл OUTPUT.TXT выведите нижнее и верхнее значение игры через пробел.

Примеры

INPUT.TXTOUTPUT.TXT
13 3
4 -1 -3
-2 1 3
0 2 -3
-2 2
23 4
-1 0 2 1
-2 0 1 0
2 1 -1 -2
-1 1

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483