Fişierul intrare/ieşire:joc.in, joc.outSursăpreOJI 2004
AutorMircea Bogdan PasoiAdăugată de
Timp execuţie pe test0.45 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

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

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!

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.

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.

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

Exemplu

joc.injoc.out
1 6
2 1 3 4 0 5
3 1 6

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content