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 K1, K2, . . . , KN , să se determine pentru fiecare valoare Ki (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 Ki 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

Exemplu

Explicaţie

...

Cum se trimit solutii?