Doamna directoare trebuie să împartă elevii din clasele a VII-a în k grupe pentru un concurs. Numărul de elevi din oricare două grupe trebuie să difere cel mult cu 1, iar numărul de fete şi de băieţi din fiecare grupă trebuie să difere tot cu cel mult 1. Ştiind că sunt maxim 200 de elevi în clasele a VII-a, doamna directoare, după ce formează grupele, doreşte să fie verificat dacă acestea sunt bine realizate (fiecare copil să apară într-o singură grupă şi grupele să satisfacă condiţiile cerute).
Exemplu:
Pentru 10 copii în clasele a VII-a, un număr de 3 grupe, şirul care indică componenţa fete sau băieţi: fbfbfbfbfb cu semnificaţia copilul cu numărul de ordine 1 este fată, cel cu numărul 2 este băiat, etc..
Prima grupă are 3 copii şi componenţa : 1 2 10
Grupa a doua are 3 copii şi componenţa : 3 4 9
Grupa a treia are 4 copii şi componenţa : 5 6 7 8
Răspunsul este: grupele au fost corect alcătuite.
Numerele ce formează o grupă reprezintă numărul de ordine pe care îl are fiecare copil în şirul iniţial.
Cerinţă
Scrieţi un program care, cunoscând numărul total de copii, numărul de grupe, un şir format din caracterele f şi b pentru fiecare copil dacă este fată sau băiat, numărul de copii din fiecare grupă şi componenţa grupelor, răspunde prin DA sau NU dacă s-au constituit corect sau nu grupele de copii. Pentru fiecare grupă se va preciza numărul de fete şi numărul de băieţi din grupa respectivă. Grupele sunt corect constituite dacă sunt cuprinşi toţi copiii, numărul de copii din grupe diferă prin cel mult un copil şi pentru fiecare grupă numărul de fete şi de băieţi diferă prin cel mult 1.
Date de intrare
Fişierul grupe1.in conţine pe prima linie numerele naturale n şi k, reprezentând numărul de elevi din clasele a VII-a şi respectiv numărul de grupe pe care doreşte să-l realizeze directoarea. Pe următoarea linie se află un şir de n caractere f şi b format astfel: dacă elevul cu numărul de ordine i este fată, caracterul de pe poziţia i din şir este f; dacă elevul cu numărul de ordine i este băiat, caracterul de pe poziţia i din şir este b. Următoarele k linii vor avea următoarea structură: numărul de copii din grupă urmat de numerele de ordine ale copiilor care formează grupa respectivă.
Date de ieşire
Fişierul de ieşire grupe1.out va conţine pe primele k linii câte două valori numere naturale reprezentând numărul de băieţi şi numărul de fete din fiecare grupă, separate prin câte un spaţiu şi pe ultimul rând cuvântul DA dacă grupele sunt constituite corect sau cuvântul NU în caz contrar.
Restricţii
1 ≤ n ≤ 200
1 ≤ k ≤ 200
Exemple
grupe1.in
grupe1.out
Explicaţii
10 3
fbfbfbfbfb
3 1 2 10
3 3 4 9
4 5 6 7 8
2 1
1 2
2 2
DA
Numărul de copii din grupe este 3, 3, 4, deci diferă prin cel mult 1; în prima grupă sunt 2 băieţi şi o fată, în grupa a doua sunt 2 fete şi un băiat, iar în grupa a treia sunt 2 fete şi 2 băieţi
10 2
fffffbbbbb
7 1 2 3 4 6 7 8
3 5 9 10
3 4
2 1
NU
Numarul de copii din prima grupa este 7 iar din grupa a doua 3, deci diferă prin mai mult decât 1 copil