Fişierul intrare/ieşire:gramezi.in, gramezi.outSursă.campion 2007, Runda 11
AutorMircea Bogdan PasoiAdăugată dedominoMircea Pasoi domino
Timp execuţie pe test0.025 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

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.ingramezi.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content