| Fişierul intrare/ieşire: | game1.in, game1.out | Sursă | ad-hoc |
| Autor | Adăugată de |  Boaca Cosmin •darkseeker | |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Game1
Aceasta problema are dificultate medie.
Doi jucători joacă următorul joc:
Ei au o tablă de (M + 1) x (N + 1) celule. Pe linia M + 1 şi pe coloana N + 1 se regăsesc valori pozitive.
În colţul din stânga sus al tablei, celula (1, 1), se află un jeton pe care cei doi îl mută alternativ. O mutare constă în deplasarea jetonului în jos sau în dreapta. Mai formal, din celula (i, j) jetonul se poate muta în celula (i + 1, j) sau (i, j + 1).
Dacă jetonul ajunge pe ultima linie sau pe ultima coloană, jocul se termină şi jucătorul 1 câştigă un număr de puncte egal cu valoarea aflată în celula în care a ajuns jetonul.
Prima mutare este efectuată de jucăţorul 1.
Considerând că amândoi jucătorii joacă perfect, care este câştigul maxim pe care îl poate câştiga primul jucătorul 1 ?
Date de intrare
Fişierul de intrare game1.in conţine pe prima linie numerele M şi N, pe linia a doua N numere întregi, reprezentând valorile de pe linia M + 1 coloanele 1 - N, iar pe linia a treia M numere reprezentând valorile de pe coloana N + 1, liniile 1 – M. Pe poziţia (M + 1,N + 1) putem considera că se află numărul 0, poziţia fiind inaccesibilă, în condiţiile jocului.
Date de ieşire
Fişierul de ieşire game1.out va conţine o singură linie pe care va fi scris un număr reprezentând câştigul maxim al jucătorului 1.
Restricţii
- M, N ≤ 200
- Valorile din celule sunt numere mai mici sau egale cu 4000
Exemplu
| game1.in | game1.out |
|---|---|
| 2 2 2 1 3 4 | 3 |
Explicaţie
Matricea arată în felul următor:
X . 3
. . 4
2 1 0
X reprezintă jetonul, iar . reprezintă o celulă goală.
Jucătorul unu va muta jetonul către dreapta ajungându-se la starea:
. X 3
. . 4
2 1 0
Jucătorul 2 poate muta în celula cu valoare 3 terminând jocul cu scorul 3, sau poate muta în jos, urmând ca jucătorul 1 să mute în dreapta terminând jocul cu scorul 4. Cum ambii jucători joacă perfect jucătorul 2 va alege varianta care îi minimează pierderea deci va termina jocul cu scorul 3.
