Školsko natjecanje iz informatike 2017. / Srednja škola / Druga podskupina (3. i 4. razred) - 3. zadatak

Papir je jednostavna igra za jednog igrača za koju je potrebna samo jedna dugačka traka papira te vodene bojice. Traka papira je podijeljena na n jednakih kvadratića koji se protežu jedan za drugim slijeva na desno, a svaki kvadratić je obojen u jednu od 26 boja. Igrač pokušava sve kvadratiće obojiti u istu (proizvoljnu) boju u što manje koraka. U jednom koraku igrač odabere proizvoljan niz uzastopnih kvadratića iste boje te ih sve oboji u istu (ali neku drugu) boju.

Boje označavamo malim slovima engleske abecede. Na primjer, ako je početna traka “aaabccbbba”, onda igrač može završiti igru u dva koraka: najprije dva uzastopna kvadratića boje “c” oboji u boju “b” i dobije “aaabbbbbba”, zatim 6 uzastopnih kvadratića boje “b” oboji u boju “a”. Zadana je traka, odredite najmanji broj koraka potreban da igrač završi igru.

Ulazni podaci

U prvom redu nalaze se prirodni broj n (n ≤ 40) — broj kvadratića na traci. U sljedećem redu nalazi se niz od n malih slova engleske abecede — i-ti znak označava boju i-tog kvadratića trake.

Izlazni podaci

U prvi red ispišite traženi najmanji broj koraka.

Bodovanje

• U test podacima vrijednim 30% bodova se samo pojavljuju boje “a” i “b”.
• U dodatnim test podacima vrijednim 30% bodova vrijedi 1 ≤ n ≤ 20.

Primjeri test podataka

ulaz

10
aaabccbbba

izlaz

2

ulaz

9
abbababba

izlaz

3

ulaz

11
abracadabra

izlaz

6