armonioase

Armonioase

De exemplu, aplicând operaţiile de mai sus şirul vvarnnn poate fi transformat în: warnnn, warmn, warnm, vvarmn, vvarnm.

h3. **Cerinţe**

h2. 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;

   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{~1~}, val{~2~})$ 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 $val{~1~}$ apariţii pentru w şi $val{~2~}$ 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.
h2. 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.

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 $K{~1~}, K{~2~}, . . . , K{~N~}$, câte o valoare pe o linie.

h2. 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 = 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 $K{~i~}$ 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$.

* lungimea şirului dat $2 ≤ lg ≤ 200 000$
* $2 ≤ N ≤ 10 000$

* $1 &le; Ki < lg$, pentru orice $1 &le; i &le; N$

* $1 &le; K{~i~} < lg$, pentru orice $1 &le; i &le; 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$ |

| 4 | 10 | $C = 3, 200 < lg &le; 200 000$, numărul total de litere w şi m este $&le; 300$ |
| 5 | 43 | $C = 3$, fără restricţii suplimentare |

h2. Exemplu

h2. Exemple

table(example). |_. armonioase.in |_. armonioase.out |
| 1

6
| NU
DA

|

|
| 2
vvamnnnvvw
| 3
|
| 3
avwmmbwmamw
| 10
|
 
h3. 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 $K{~1~} = 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 $K{~2~} = 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.
 

h3. Explicaţie
...

== include(page="template/taskfooter" task_id="armonioase") ==