== include(page="template/taskheader" task_id="pizza") ==
Poveste şi cerinţă...
Alice si Bob s-au revazut dupa mult timp la o pizzerie din estul Taiwanului. Cum niciunul nu voia sa manance o pizza intreaga, s-au hotarat sa comande o pizza mai speciala. Aceasta pizza are proprietatea ca este impartita in $N$ felii tringhiulare de dimensiuni diferite. Pentru a nu preciza ca o anumita felie reprezinta $x%$ din intreaga pizza, bucatarul a scris cu sos pe fiecare felie un numar natural mai mare ca 0 reprezintand astfel o valoare ce aproximeaza acest procent. Mai exact, in acest caz, o felie marcata cu valoarea $10$ va fi de doua ori mai mare decat o felie marcata cu valoarea $5$.
h2. Cerinţă
Pentru ca Alice si Bob sunt mari fani ai pizzei, ei doresc sa manance individual cat mai multa pizza. Cum acest tip de pizza este special, ei au creat anumite reguli pentru ca jocul sa fie corect.
* Fiecare mananca alternativ cate o felie de pizza.
* Alice este cea care alege de unde ia prima felie
* Dupa ce Alice extrage prima felie, fiecare are voie sa aleaga doar o felie adiacenta cu portiunea de pizza deja extrasa.
Fiecare din cei doi copii vor dori sa manance o cantitate cat mai mare de pizza, astfel incat fiecare va avea o strategie optima de extragere a feliilor pentru a manca o catintate maxima posibil de pizza. Se intelege prin cantitate de pizza mancata de unul dintre copii ca suma valorilor de pe feliile de pizza extrase de acesta.
Bucatarul este foarte interesat de acest joc al copiilor si va roaga pe voi sa calculati care este valoarea maxima pe care o poate extrage Alice si Bob, fiecare jucand optim si sa ii spuneti diferenta dintre valoarea obtinuta de Alice si valoarea obtinuta de Bob.
h2. Date de intrare
Fişierul de intrare $pizza.in$ ...
Fişierul de intrare $pizza.in$ contine pe prima linie valoarea $N$ reprezentand numarul total de felii.
Pe urmatoarea linie se va descrie configuratia feliilor de pizza. Mai exact, se vor citi $N$ numere naturale mai mari ca $0$ ce vor reprezenta valorile scrise pe $N$ bucati de pizza consecutive (prima felie este aleasa la intamplare). Se precizeaza ca pe blatul de pizza, a $N$ felie citita se afla inaintea primei felii citite.
h2. Date de ieşire
În fişierul de ieşire $pizza.out$ ...
În fişierul de ieşire $pizza.out$ se va afla un singur numar intreg reprezentand diferenta dintre valoarea obtinuta de Alice si valoarea obtinuta de Bob.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $2 ≤ N ≤ 5 000$
* $1 ≤ X ~i~ ≤ 10 000, unde X ~i~ reprezinta valoarea scrisa pe a i -a felie de pizza$
* $De reţinut faptul ca Antonio şi Antonia iubesc pizza!$
h2. Exemplu
table(example). |_. pizza.in |_. pizza.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 7
7 8 3 10 2 5 7
| 8
|
h3. Explicaţie
...
!> problema/pizza?pizza.png 100%!
Fiecare copil va juca optim astfel incat se vor extrage pe rand urmatoarele felii de pizza:
* Alice: Felia cu numarul $10$
* Bob: Felia cu numarul $2$
* Alice: Felia cu numarul $5$
* Bob: Felia cu numarul $7$
* Alice: Felia cu numarul $7$
* Bob: Felia cu numarul $8$
* Alice: Felia cu numarul $3$
Alice extrage felii cu valoarea totala de $25$, iar Bob extrage felii cu valoarea totala de $17$.
Diferenta dintre suma obtinuta de Alice si Bob este $25 - 17 = 8$ .
== include(page="template/taskfooter" task_id="pizza") ==
