Fişierul intrare/ieşire:charlie.in, charlie.outSursăOJI 2015 clasa a 10-a
AutorEugen NodeaAdăugată deCatalin.FrancuCatalin Francu Catalin.Francu
Timp execuţie pe test0.5 secLimită de memorie4096 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise

Charlie (clasa a 10-a)

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 ş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.

Exemplu

charlie.incharlie.outExplicaţ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).
Trebuie sa te autentifici pentru a trimite solutii. Click aici