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.