| Fişierul intrare/ieşire: | gramezi.in, gramezi.out | Sursă | .campion 2007, Runda 11 |
| Autor | Mircea Bogdan Pasoi | Adăugată de |  Mircea Pasoi •domino |
| Timp execuţie pe test | 0.025 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate |   2/5 |
Vezi solutiile trimise | Statistici
Gramezi
Zaharel si Bronzarel joaca urmatorul joc: se pun pe masa N gramezi de monede. Se stie ca daca Zaharel ia gramada i primeste Ai din monedele din gramada, iar daca Bronzarel ia gramada i primeste Bi din monedele din gramada (se stie ca fiecare gramada are cel putin max(Ai, Bi) monede iar monedele care raman se arunca). Cei doi jucatori iau alternativ cate o gramada, pana cand se epuizeaza toate cele N, iar Zaharel este primul care ia o gramada. La final, castiga jucatorul cu mai multe monede. Daca cantitatile de monede sunt egale, jocul se considera remiza.
Stiind ca Zaharel si Bronzarel joaca optim, determinati numarul de monede pe care il va avea fiecare jucator la final. Prin joc optim se intelege ca fiecare jucator incearca sa mareasca diferenta dintre numarul de monezi pe care le detine si numarul de monezi ale celuilalt jucator, iar in cazul in care are mai multe posiblitati de a obtine aceeasi diferenta va incerca sa-si mareasca numarul de monede.
Date de intrare
Pe prima linie a fisierului de intrare gramezi.in este scris numarul natural N. Pe urmatoarele N linii se vor gasi cate doua numere naturale separate prin cate un spatiul, reprezentand valorile Ai, respectiv Bi.
Date de iesire
Prima linie a fisierului gramezi.out va contine doua numere naturale separate prin spatii reprezentand scorul lui Zaharel, respectiv scorul lui Bronzarel.
Restrictii
- 1 ≤ N ≤ 30.000
- 1 ≤ Ai, Bi ≤ 30.000
Exemplu
| gramezi.in | gramezi.out |
|---|---|
| 4 2 10 5 5 7 3 4 1 | 9 6 |
Explicatie
Zaharel ia gramada 1, apoi Bronzarel ia gramada 2, apoi Zaharel ia gramada 3, apoi Bronzarel ia gramada 4. O alta posiblitate de joc cu aceeasi diferenta de scor este urmatoarea: Zaharel ia gramada 1, apoi Bronzarel ia gramada 3, apoi Zaharel ia gramada 2, apoi Bronzarel ia gramada 4. Astfel, s-ar fi obtinut scorurile 7, respectiv 4, dar acestea sunt mai mici decat in prima varianta.
