| Fişierul intrare/ieşire: | charlie.in, charlie.out | Sursă | OJI 2015, clasa a 10a |
| Autor | Eugen Nodea | Adăugată de |  FMI Suditu Thomas •Thomas |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 8192 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Charlie
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.
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: Li > Li+1 < Li+2 > Li+3 < Li+4 > … < Lj.
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.
Date de intrare
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.
Date de ieşire
Dacă valoarea lui p este 1, se va rezolva numai punctul a) din cerinţă.
Î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ţă.
Î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ă.
Restricţii
- 3 ≤ numărul de litere ale şirului iniţial ≤ 100000
- 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 ≤ 1000
Exemplu
| charlie.in | charlie.out |
|---|---|
| 1 cadgfacbda | 5 |
| 2 cbcabadbac | ccdc 21 |
Explicaţie
În primul exemplu p = 1
Secvenţele alternante corect formate sunt: cad, facbd. Lungimea maximă este 5
În al doilea exemplu p = 2
Şirul iniţial: cbcabadbac
Eliminăm din secvenţa bad litera a şi adăugăm la suma valoarea 4
Şirul rezultat în urma eliminării este: cbcabdbac
Eliminăm din secvenţa bac litera a şi adăugăm la suma valoarea 3
Şirul rezultat în urma eliminării este: cbcabdbc
Eliminăm din secvenţa dbc litera b şi adăugăm la suma valoarea 4
Şirul rezultat în urma eliminării este: cbcabdc
Eliminăm din secvenţa cab litera a şi adăugăm la suma valoarea 3
Şirul rezultat în urma eliminării este: cbcbdc
Eliminăm din secvenţa cbd litera b şi adăugăm la suma valoarea 4
Şirul rezultat în urma eliminării este: cbcdc
Eliminăm din secvenţa cbc litera b şi adăugăm la suma valoarea 3
Şirul rezultat în urma eliminării este: ccdc
Nu mai sunt posibile eliminări. Suma maximă obţinută este 21.
