==Include(page="template/taskheader" task_id="joc")==
== include(page="template/taskheader" task_id="joc") ==
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
Poveste ...
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. Date de Intrare
h2. Restrictii
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 Iesire
h2. Date de intrare
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. Restrictii si precizari
h2. Date de iesire
* $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
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.
| joc.in | joc.out |
| linia1
linia2
linia3
| linia1
linia2
|
==Include(page="template/taskfooter" task_id="joc")==
== include(page="template/taskfooter" task_id="joc") ==
