Fişierul intrare/ieşire:charlie.in, charlie.outSursăOJI 2015, clasa a 10a
AutorEugen NodeaAdăugată deThomasFMI Suditu Thomas Thomas
Timp execuţie pe test0.2 secLimită de memorie8192 kbytes
Scorul tăuN/ADificultateN/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.incharlie.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?