== include(page="template/taskheader" task_id="game") ==
Boyan se joacă un joc pe calculator. La început există $N$ bile așezate în linie. Pe fiecare bilă este scris un număr și pe oricare două bile vecine sunt numere diferite. Jocul are următorii pași:
Boyan se joacă un joc pe calculator. La început există $N$ bile așezate în linie. Pe fiecare bilă este scris un număr și pe oricare două bile vecine sunt numere diferite. Jocul are următorii pași:
1. Jucătorul șterge o bilă dintre cele date.
2. Cât timp există bile consecutive cu același număr, acestea sunt automat șterse din linie.
3. Dacă mai rămân bile, se merge la pasul 1, altfel jocul se termină.
3. Dacă mai rămân bile, se merge la pasul 1, altfel jocul se termină.
Scorul este numărul total de bile șterse automat. Scopul este să se maximizeze scorul.
Scorul este numărul total de bile șterse automat.
Scopul este să se maximizeze scorul.
Să considerăm un exemplu cu 6 bile, numerotate {[$1$], [$2$], [$3$], [$2$], [$1$], [$5$]}.
1. Boyan șterge bila cu numărul [$3$].
1. Boyan șterge bila cu numărul [$3$].
Bilele rămare sunt: {[$1$], [$2$], [$2$], [$1$], [$5$]}.
2. Ștergând bilele vecine pe care este scrisă aceeași valoare, avem:
{[$1$], [$2$], [$2$], [$1$], [$5$]} -> {[$1$], [$1$], [$5$]} -> [$5$].
2. Ștergând bilele vecine pe care este scrisă aceeași valoare, avem:
{[$1$], [$2$], [$2$], [$1$], [$5$]} -> {[$1$], [$1$], [$5$]} -> [$5$].
Bila rămasă este [$5$].
3. Mai rămân bile, deci se merge la pasul 1.
1. Boyan șterge bila cu numărul [$5$].
1. Boyan șterge bila cu numărul [$5$].
Bilele rămase: {}.
2. Nu sunt bile vecine pe care este scris acela și număr.
3. Nu mai sunt bile rămase, deci se termină jocul.
Numărul de bile șterse automat este [$4$].
Numărul de bile șterse automat este [$4$].
Acesta este scorul maxim posibil pentru acest joc.
Boyan este un jucător bun, dar nu este sigur că joacă mereu optim.
Scrieți un program care să îl ajute să obțină cel mai mare scor posibil.
Boyan este un jucător bun, dar nu este sigur că joacă mereu optim.
Scrieți un program care să îl ajute să obțină cel mai mare scor.
h2. Date de intrare
Fișierul de intrare $game.in$ conține pe prima linie un întreg pozitiv [$N$].
Pe a doua linie conține $N$ întregi pozitivi reprezentând numerele scrise pe bile.
h2. Date de ieșire
În fișierul de ieșire $game.out$ se va afișa scorul maxim pe care Boyan îl poate obține.
* În $20%$ dintre teste N ≤ $10$
* În $50%$ dintre teste N ≤ $100$
h2. Exemplu
table(example).
|_. game.in |_. game.out |
|6
1 2 3 2 1 5
|4
|
|9
1 5 1 3 2 4 2 3 1
|6
| $6$
$1$ $2$ $3$ $2$ $1$ $5$
| $4$
|
| $9$
$1$ $5$ $1$ $3$ $2$ $4$ $2$ $3$ $1$
|[$6$]
|
h3. Explicație
În al doilea exemplu se șterg bilele de pe pozițiile: [$2$], $6$ și [$9$].
Se șterg a $9$ - a, a $6$ - a și a $2$ - a bilă
== include(page="template/taskfooter" task_id="game") ==
