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.
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
h3. Explicație
* $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$.
...
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") ==
