== include(page="template/taskheader" task_id="charlie") ==
Poveste și cerință...
_*Charlie*_ a decis să se joace cu literele dintr-un șir de caractere, șir ce conține doar literele mici ale alfabetului englez $'a'...'z'$. Jocul constă în a elimina litere din șir după următoarea regulă: fie $L1, L2, L3$ trei litere aflate pe poziții consecutive în șir, atunci litera $L2$ poate fi eliminată dacă și numai dacă este strict mai mică lexicografic decât literele $L1$ și [$L3$].
Pentru a face jocul mai interesant, _*Charlie*_ atașează eliminării literei $L2$ un cost egal cu valoarea maximă dintre $ō(L1)$ și $ō(L3)$, unde prin $ō(litera)$ înțelegem numărul de ordine al literei respective în alfabet $(ō('a')=1, ō('b')=2, ..., ō('z')=26)$. _*Charlie*_ aplică în mod repetat procedeul de eliminare și calculează suma costurilor eliminărilor efectuate.
h2. Cerințe
Fiind dat un șir de caractere să se determine:
a) Lungimea maximă a unei secvențe de litere alternante, adică o secvență pentru care literele aflate pe poziții consecutive sunt de forma: $L[~i~] > L[~i+1~] < L[~i+2~] > L[~i+3~] < L[~i+4~] > ... < L[~j~]$.
b) Suma maximă pe care o poate obține _*Charlie*_ aplicând în mod repetat procedeul de eliminare a literelor, precum și șirul obținut în final.
h2. Date de intrare
Fișierul de intrare $charlie.in$ ...
Fișierul de intrare $charlie.in$ conține pe prima linie un număr natural [$p$]. Pentru toate testele de intrare, numărul $p$ poate avea doar valoarea $1$ sau valoarea [$2$]. Pe următoarea linie se află un șir de caractere.
h2. Date de ieșire
În fișierul de ieșire $charlie.out$ ...
Dacă valoarea lui $p$ este [$1$], *se va rezolva numai punctul a)* din cerință.
h2. Restricții
În acest caz, în fișierul de ieșire $charlie.out$ se va scrie un singur număr natural $L$ ce reprezintă lungimea maximă a unei secvențe de litere alternante.
* $... ≤ ... ≤ ...$
Dacă valoarea lui $p$ este [$2$], *se va rezolva numai punctul b)* din cerință.
h2. Exemplu
În acest caz, fișierul de ieșire $charlie.out$ va conține două linii. Pe prima linie se va afla șirul rezultat în urma eliminărilor repetate de litere respectând regula enunțată, iar pe cea de-a doua linie suma maximă obținută.
table(example).
|_. charlie.in |_. charlie.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h2. Restricții și precizări
* $3 ≤$ numărul de litere ale șirului inițial $≤ 100.000$
* Pentru rezolvarea corectă a primei cerințe se acordă $25$ de puncte, iar pentru cerința a doua se acordă $75$ de puncte.
* Pentru $30%$ dintre teste numărul de litere ale șirului $≤ 1.000$.
h3. Explicație
h2. Exemplu
...
table(example).
|_. charlie.in |_. charlie.out |_. Explicație |
| 1
cadgfacbda
| 5
| p = 1
Secvențele alternante corect formate sunt: *cad, facbd.* Lungimea maximă este 5.
*Atenție! Pentru acest test se rezolvă doar cerința a).*
|
| 2
cbcabadbac
| ccdc
21
| p = 2
Șirul inițial: *cbcabadbac*
Eliminăm din secvența *bad* litera *a* și adăugăm la sumă valoarea 4
Șirul rezultat în urma eliminării este: *cbcabdbac*
Eliminăm din secvența *bac* litera *a* și adăugăm la sumă valoarea 3
Șirul rezultat în urma eliminării este: *cbcabdbc*
Eliminăm din secvența *dbc* litera *b* și adăugăm la sumă valoarea 4
Șirul rezultat în urma eliminării este: *cbcabdc*
Eliminăm din secvența *cab* litera *a* și adăugăm la sumă valoarea 3
Șirul rezultat în urma eliminării este: *cbcbdc*
Eliminăm din secvența *cbd* litera *b* și adăugăm la sumă valoarea 4
Șirul rezultat în urma eliminării este: *cbcdc*
Eliminăm din secvența *cbc* litera *b* și adăugăm la sumă valoarea 3
Șirul rezultat în urma eliminării este: *ccdc*
Nu mai sunt posibile eliminări. Suma maximă obținută este 21.
Atenție! Pentru acest test se rezolvă doar cerința b).
|
== include(page="template/taskfooter" task_id="charlie") ==
