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.
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: |
Timp maxim de executie/test: 0.1 secunde
prof. Emanuela Cerchez
Liceul de
Informatica "Grigore Moisil" Iasi
Contact:emanuela.cerchez@gmail.com