De Crăciun la grădiniţa Pinochio
se organizează o serbare. În cadrul acestei serbări copii alcătuiesc o
horă. Educatoarea doreşte ca la un semn făcut de ea să iasă din horă unii
copii astfel incat sa se obţina o noua hora în care să nu existe doi băieţi
sau două fete una lângă alta. Hora este dată prin prenumele (unul singur)
al fiecărui copil, băieţii având la sfârşit caracterul '*'.
Aceste prenume sunt separate prin unul sau mai multe spaţii.
Cerinţă
Să se scrie un program care să determine minim
de copii care trebuie să iasă din horă pentru a respecta cerinţa din enunţ.
Date de intrare
Fişierul de intrare hora.in
are pe prima linie şirul de caractere cu numele copiilor.
Date de ieşire
Fişierul de ieşire hora.out
va conţine pe prima linie numărul cerut.
Restricţii
Şirul de caractere din fişierul de intrare este
alcătuit din maxim 145000 caractere, litere mari şi mici ale alfabetului
englez, spaţii şi caracterul * (folosit numai pentru sfârşitul prenumelui
băieţilor).
Numele copiilor nu au mai mult de 8 litere.
Ultimul copil este legat în horă de primul.
Hora are cel puţin un băiat şi cel puţin o fată
Exemple
hora.in
hora.out
Explicaţii
Alin* Dan* Maria
Anca Florinel* Dan*
4
De exemplu se
pot elimina din horă copii Alin, Maria, Florinel, Dan, rămânând
o horă doar cu Dan şi Maria.