Teoria dei giochi

Nella teoria dei giochi uno dei concetti più interessanti è il gioco a somma zero per due giocatori.

Questi giochi sono caratterizzati da un insieme X di strategie per il primo giocatore e da un insieme Y di strategie per il secondo giocatore.
Viene poi stabilita la funzione delle vincite K(x,y} con x in X e y in Y.
Se X e Y sono insiemi finiti si parla di gioco matriciale perché la funzione delle vincite può essere rappresentata da una matrice.

Consideriamo un gioco matriciale con X ={ 1,…, n } e Y ={ 1,…, m } e denotiamo la matrice con K.

Così Kij è la vincita del primo giocatore quando sceglie la strategia i assumendo che il secondo giocatore scelga la strategia j.
Se questo valore è positivo si tratta effettivamente di una vincita.
Se invece è negativo si tratta di una perdita (e quindi di una vincita per il secondo giocatore).

Il valore di maximin di questo gioco è maxi=1…n minj=1…m Kij.
Il valore di minimax di questo gioco è invece minj=1…m max<sub>i=1…n</sub> Kij.

Data una matrice delle vincite di un gioco matriciale si chiede di calcolare i suoi valori di maximin e di minimax.

Dati di input

La prima riga del file di input contiene due numeri interi n ed m (1 <= n, m <= 100).
Ciascuna delle n righe successive contiene m numeri interi.
Il j-esimo numero della i-esima di queste righe contiene Kij.
Tutti i Kij non superano 100 in valore assoluto.

Dati di output

Dare in uscita i valori di maximin e di minimax.

Esempio

input.txt output.txt
3 3
4 -1 -3
-2 1 3
0 2 -3
-2 2
3 4
-1 0 2 1
-2 0 1 0
2 1 -1 -2
-1 1

Autore/i: A.S. Stankevich, ACM ICPC Team St. Petersburg State University of Information technology, Mechanics and Optics.