Pe data de 13 Decembrie se serbează Ziua Națională a Țării Piticilor. Cu această ocazie va avea loc Parada Militară a Armatei Piticilor.
Deoarece se cunoaște preferința pentru simetrie a Piticului Șef, conducătorul paradei militare, Generalul Pitic, știe că soldații pitici vor trebui să defileze în șir indian și culorile scufiilor piticilor trebuie să urmeze în aceeași succesiune indiferent de direcția din care sunt priviți piticii care defilează. Cu alte cuvinte, scufia primului pitic trebuie să aibă aceeași culoare ca scufia ultimului pitic, scufia celui de-al doilea pitic trebuie să aibă aceeași culoare cu cea a penultimului pitic și așa mai departe. După ce și-a aranjat soldații astfel încât această cerință să fie respectată, Generalul Pitic, a plecat să stabilească ultimele detalii pentru ca parada să se desfășoare în cele mai bune condiții. Din nefericire, în acest timp, soldații au fost vizitați de Miss Pitic și, în momentul în care au văzut-o, aceștia au rupt imediat rândurile (de fapt, rândul). Când au auzit că Generalul Pitic se întoarce, piticii au format repede un nou rând dar, evident, acesta nu mai era simetric. Generalul Pitic s-a întors și a observat dezastrul produs; s-a alarmat și a vrut să anuleze parada datorită faptului că și-a dat seama că în timpul rămas nu va reuși să rearanjeze soldații pitici. Din fericire, consilierului său, Colonelul Pitic, i-a venit o idee care ar putea salva situația. Soluția sa este ca anumiți pitici să iasă din rând și rândul rămas să fie simetric. Generalul Pitic a agreat această idee (de fapt, nu prea avea de ales) și i-a cerut unui pitic de încredere (Caporalul Pitic), să aleagă piticii care trebuie să iasă din rând pentru ca șirul simetric obținut să fie cât mai lung posibil (dorea ca parada să dureze cât mai mult, chiar și în aceste condiții). Așadar, cunoscând succesiunea culorilor scufiilor din rândul pe care l-au format soldații după vizita lui Miss Pitic, va trebui să determinați numărul minim de pitici care trebuie să părăsească șirul pentru ca acesta să rămână simetric.
Prima linie a fișierul de intrare PARADE.IN conține numărul N al piticilor care ar fi trebuit să participe la paradă. Pe fiecare dintre următoarele N linii se află câte un șir de caractere care reprezintă culoarea scufiei unui pitic din șir. Ordinea în care sunt descrise culorile scufiilor este dată de ordinea în care se află piticii după vizita lui Miss Pitic.
Fișierul de ieșire PARADE.OUT trebuie să conțină o singură linie pe care se va afla numărul minim al piticilor care trebuie să părăsească șirul.
PARADE.IN
5 red green blue blue red PARADE.OUT 1
Doar piticul cu scufie verde (green) trebuie să părăsească șirul. Vor rămîne patru pitici; primul va avea scufie roșie (red), următorii doi scufie albastră (blue), iar ultimul sufie roșie (red). Așadar, șirul piticilor va fi simetric.
|