== include(page="template/taskheader" task_id="joc") ==
==Include(page="template/taskheader" task_id="joc")==
Poveste ...
Gicu si Nicu, olimpici la informatica si buni prieteni, mereu incearca sa imbine activitatile lor cu informatica. Spre exemplu, cand se plictisesc in ore ei joaca un joc, bazat pe urmatoarele reguli:
* fie o matrice cu numere intregi cu $N$ linii si $M$ coloane
* fiecare jucator muta alternativ un jeton plasat pe un element din matrice
* o mutare consta in plasarea jetonului pe o alta pozitie si adaugarea valorii din matrice de pe pozitia respectiva la scorul jucatorului care a facut mutarea; odata plasat jetonul pe o pozitie, jucatorul urmator poate sa mute jetonul doar pe o alta pozitie din dreptunghiul format de coltul stanga-sus si pozitia curenta a matricei
* jocul se termina cand un jucator ajunge cu jetonul in coltul stanga-sus al matricei
* la inceputul jocului, ambii jucatori au scor {$0$}, iar jucatorul care incepe alege pozitia initiala a jetonului
h2. Cerinta
...
Presupunand ca fiecare din cei doi joaca optim, si ca Gicu va incepe jocul, determinati pozitia initiala a jetonului, astfel incat diferenta de scor intre Gicu si Nicu sa fie maxima!
h2. Restrictii
h2. Date de Intrare
...
Prima linie a fisierului $joc.in$ contine doua numere intregi $N$ si {$M$}, separate prin cate un spatiu, care reprezinta numarul de linii si coloane ale matricii. Urmatoarele $N$ linii contin cate $M$ numere intregi, separate prin cate un spatiu, care descriu matricea.
h2. Date de intrare
h2. Date de Iesire
...
Fisierul $joc.out$ va contine trei numere intregi separate prin cate un spatu: diferenta maxima de scor intre Gicu si Nicu si linia si coloana unde se va plasa jetonul la inceputul jocului.
h2. Date de iesire
h2. Restrictii si precizari
...
* $1 ≤ N, M ≤ 1.000$
* Valorile din matrice sunt cuprinse in intervalul [{$-1.000, 1.000$}]
* Liniile sunt numerotate de la $1$ la {$N$}, iar coloanele de la $1$ la $M$
* Prin joc optim se intelege ca Gicu va incerca sa maximizeze diferenta de scor, in timp ce Nicu va incerca sa o minimizeze
* Daca exista mai multe pozitii initiale pentru care se obtine diferenta maxima, atunci se va alege cea in care numarul liniei este cel mai mic, iar in caz de egalitate cea in care numarul coloanei este cel mai mic
h2. Exemplu
| joc.in | joc.out |
| linia1
linia2
linia3
| linia1
linia2
|
table(example). |_. joc.in |_. joc.out |
| 1 6
2 1 3 4 0 5
| 3 1 6 |
h3. Explicatii
Incepand din ({$1, 6$}) jocul optim este: Gicu ia {$5$}, Nicu ia {$4$}, Gicu ia {$2$}.
Orice alta pozitie initiala a jetonului ar fi dus la obtinerea unei diferente de scor mai mica.
== include(page="template/taskfooter" task_id="joc") ==
==Include(page="template/taskfooter" task_id="joc")==
