Joc

joc

==Include(page="template/taskheader" task_id="joc")==

== include(page="template/taskheader" task_id="joc") ==
 
Poveste ...
 
h2. Cerinta
 
...
 
h2. Restrictii
 
...
 
h2. Date de intrare
 
...
 
h2. Date de iesire
 
...
 
h2. Exemplu
 
| joc.in | joc.out |
| linia1
linia2
linia3
| linia1
linia2
|
 
== include(page="template/taskfooter" task_id="joc") ==

==Include(page="template/raw")==
 
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:
 
S fie o matrice cu numere intregi cu N linii si M coloane
 
S fiecare jucator muta alternativ un jeton plasat pe un element din matrice
 
S 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
 
S jocul se termina cand un jucator ajunge cu jetonul in coltul stanga-sus al matricei
 
S 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. 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 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. Restrictii si precizari
 
S 1 <= N, M <= 1.000
 
S Valorile din matrice sunt cuprinse in intervalul [-1.000, 1.000]
 
S Liniile sunt numerotate de la 1 la N, iar coloanele de la 1 la M
 
S Prin joc optim se intelege ca Gicu va incerca sa maximizeze diferenta de scor, in timp ce Nicu va incerca sa o minimizeze
 
S 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 Explicatie
1 6 3 1 6 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.
 
2 1 3 4 0 5
 
 
 
 
==Include(page="template/taskfooter" task_id="joc")==