Ana
si Barbu joaca un nou joc. In acest joc se aseaza pe masa un sir format dintr-un
numar par de carti. Cartile sunt puse cu fata in sus si pe fiecare carte este
scris un numar natural.
Jucatorii muta alternativ (Ana incepe jocul). Jucatorul care este la mutare
poate lua o singura carte de la unul dintre cele doua capete ale sirului si
o plaseaza in teancul propriu.
Jocul este castigat de jucatorul care obtine cea mai mare suma a numerelor scrise
pe cartile din teancul sau.
Barbu utilizeaza o strategie "greedy" in sensul ca la fiecare pas
alege de la cele doua capete cartea cu valoarea maxima. În cazul în care are de ales între două cărţi cu valoare egală, Barbu alege întotdeauna cartea din capătul din stânga.
Cerinta Scrieti un program care sa determine pentru o anumita configuratie de joc diferenta
maxima dintre scorul Anei si scorul lui Barbu (care aplica strategia greedy).
Date
de intrare Fisierul de intrare joc.in contine
o singura linie pe care sunt scrise numere naturale separate prin cate un spatiu.
Primul numar de pe linie este n,
numarul de carti din sir. Urmatoarele n
valori reprezinta, in ordine, numerele inscrise pe cartile din sir.
Date
de iesire
Fisierul de iesire joc.out va
contine o singura linie pe care va fi scris un singur numar natural reprezentand
diferenta dintre scorul Anei si scorul lui Barbu (maxima posibil).
Restrictii 2 <= n <= 1000 Suma numerelor inscrise pe cartile de joc<= 1 000 000.
Exemplu
joc.in
joc.out
Explicatie
8 2 2 1 5 3 8 7 3
5
O modalitate
in care poate decurge jocul astfel incat diferenta de punctaj sa fie maxima
este:
Ana ia cartea cu numarul 3 din dreapta.
Barbu ia cartea cu numarul 7 din dreapta.
Ana ia cartea cu numarul 8 din dreapta
Barbu ia cartea cu numarul 3 din dreapta
Ana ia cartea cu numarul 5 din dreapta.
Barbu ia cartea cu numarul 2 din stanga.
Ana ia cartea cu numarul 2 din stanga.
Barbu ia cartea cu numarul 1.
Scor total Ana: 3+8+5+2=18
Scor total Barbu: 7+3+2+1=13
Diferenta de punctaj este 5 (maxima posibil)