Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | armonioase.in, armonioase.out | Sursă | Lot Ploiești Juniori 2026, Baraj 1 |
| Autor | Mihai Nan | Adăugată de |  Antonie Aureliu Valentin •ValiAntonie123 |
| Timp execuţie pe test | 0.8 sec | Limită de memorie | 131072 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Armonioase
Gigel este un împătimit al jocurilor şi petrece ore întregi tastând pentru a-şi învinge adversarii virtuali. Într-o zi, el a descoperit că tastatura lui a început să se comporte ciudat pentru două din tastele utilizate intens pentru jocurile sale: tasta w şi tasta m. Mai exact, Gigel a observat că atunci când doreşte să scrie un mesaj şi apasă tasta w uneori în mesaj este inclusă litera w, dar alteori, pentru o singură apăsare a tastei w, este inclusă secvenţa vv. În mod similar, când încearcă să utilizeze tasta m: la o apăsare a tastei m uneori îi apare m în mesaj, dar alteori apare secvenţa nn. Orice altă tastă funcţionează corect. Spre exemplu, atunci când tastează cuvântul warm el poate obţine unul din următoarele cuvinte: warm – dacă totul funcţionează corect; vvarm – dacă pentru tasta w apare vv; warnn – dacă pentru tasta m apare nn; vvarnn – dacă pentru tasta w apare vv şi pentru tasta m apare nn.
Gigel a descoperit un joc pentru care trebuie să tasteze şiruri armonioase. Un şir este considerat armonios dacă conţine cel puţin o literă m şi numărul de litere w din şir divide numărul de litere m care apar în acel şir. Spre exemplu, şirul mawnmvwbdmem este considerat armonios, deoarece conţine 2 apariţii pentru w şi 4 apariţii pentru m, dar şirurile awnmvwbdmem, mawnmvwbdme sau wawnmvwbdmwe nu sunt armonioase.
Definim următoarele două operaţii care se pot aplica unui şir de caractere:
1. dacă în şir identificăm două litere consecutive vv le înlocuim cu litera w;
2. dacă în şir identificăm două litere consecutive nn le înlocuim cu litera m.
De exemplu, aplicând operaţiile de mai sus şirul vvarnnn poate fi transformat în: warnnn, warmn, warnm, vvarmn, vvarnm.
Cerinţe
Dat fiind un şir format din litere mici ale alfabetului englez, scrieţi un program care să rezolve următoarele cerinţe:
1. pentru o succesiune de N valori date K 1, K 2, ..., K N, să se determine pentru fiecare valoare K_i (1 ≤ i ≤ N) dacă, prin aplicarea a 0, 1 sau mai multe operaţii descrise în enunţ, se poate transforma şirul dat într-un şir armonios care să conţină exact K_i apariţii pentru m;
2. să se determine numărul de perechi distincte de forma (val1, val2) cu proprietatea că, prin aplicarea a 0, 1 sau mai multe operaţii din enunţ, putem transforma şirul dat într-un şir armonios care să conţină exact val1 apariţii pentru w şi val2 apariţii pentru m;
3. să se determine lungimea maximă a unei secvenţe armonioase din şirul dat, fără aplicarea niciunei operaţii; o secvenţă este formată din litere situate pe poziţii consecutive în şir.
Date de intrare
Fişierul de intrare armonioase.in conţine pe prima linie numărul natural C reprezentând cerinţa care trebuie rezolvată (1, 2 sau 3). Pe a doua linie se află un şir format din litere mici ale alfabetului englez. Dacă C = 1, pe a treia linie se află numărul natural N, iar pe următoarele N linii sunt scrise valorile K1, K2, . . . , KN , câte o valoare pe o linie.
Date de ieşire
Fişierul de ieşire armonioase.out conţine:
- dacă C = 1: N linii; pe linia i (1 ≤ i ≤ N) este scris mesajul DA dacă, prin aplicarea a 0, 1 sau mai multe operaţii din enunţ, se poate transforma şirul dat într-un şir armonios care să conţină exact Ki apariţii pentru m, respectiv mesajul NU în caz contrar.
- dacă C = 2 sau 3: o singură linie pe care este scris un număr natural reprezentând răspunsul la cerinţa C.
Restricţii şi precizări
- lungimea şirului dat 2 ≤ lg ≤ 200 000
- 2 ≤ N ≤ 10 000
- 1 ≤ Ki < lg, pentru orice 1 ≤ i ≤ N
- Se garantează că în şirul dat există cel puţin o literă w şi o literă m.
| # | Punctaj | Restricţii |
|---|---|---|
| 1 | 20 | C = 1 |
| 2 | 15 | C = 2 |
| 3 | 12 | C = 3, 2 ≤ lg ≤ 200 |
| 4 | 10 | C = 3, 200 < lg ≤ 200 000, numărul total de litere w şi m este ≤ 300 |
| 5 | 43 | C = 3, fără restricţii suplimentare |
Exemplu
| armonioase.in | armonioase.out |
|---|---|
| 1 annnvvwmmbnnwmavmwv 2 5 6 | NU DA |
| 2 vvamnnnvvw | 3 |
| 3 avwmmbwmamw | 10 |
Explicaţii
Pentru primul exemplu:
C = 1. Şirul conţine 4 litere m şi 3 litere w. Nu putem obţine un şir armonios cu K1 = 5 apariţii ale literei m, deoarece 5 are exact 2 divizori (1 şi 5), deci ar trebui să avem fie 1, fie 5 litere w. Fiindcă există deja 3 litere w şi doar o pereche vv care ar putea fi transformată într-un w, nu putem obţine 5 litere w.
Pentru K2 = 6 răspunsul este DA, deoarece 3 (numărul de litere w) divide pe 6.
Pentru al doilea exemplu:
C = 2. Perechile pentru care putem obţine un şir armonios sunt: (1, 1) (exemplu: vvamnnnvvw), (1, 2) (exemplu: vvammnvvw) şi (2, 2) (exemplu: wammnvvw).
Pentru al treilea exemplu:
C = 3. Cea mai lungă secvenţă armonioasă este avwmmbwmam, care conţine două apariţii ale literei w şi 4 apariţii ale literei m. Cum 2 | 4, secvenţa este armonioasă. Aceasta are lungimea 10 şi nu există nicio secvenţă mai lungă care să respecte condiţia.
