Školsko natjecanje iz informatike 2017. / Srednja škola / Prva podskupina (1. i 2. razred) - 2. zadatak

Mirko izrađuje dekorativnu traku papira pomoću tempera. Traka je podijeljena na n jednakih kvadratića koji se protežu jedan za drugim slijeva na desno. Mirko ima na raspolaganju jednobojne trake svih mogućih boja te može odabrati bilo koju kao početnu. Nakon što odabere traku, on mora obojiti neke od kvadratića tako da konačna traka točno odgovara zadanom uzorku. Mirko traku boja na sljedeći način:

• Mirko boja kvadratić po kvadratić slijeva nadesno, preskačući kvadratiće čija boja, u konačnom uzorku, odgovara boji početne trake.

• Mirko mora očistiti kist te ga ponovo umočiti u boju:

• Na početku cijelog procesa bojanja trake.
• Ako mijenja boju s kojom boja.
• Ako je već obojao tri kvadratića nakon što je zadnji put čistio kist, a još nije gotov s bojanjem.

Bojanje jednog kvadratića traje jednu sekundu, a čišćenje kista te umakanje kista u boju traje sve skupa jednu sekundu. Smatramo da za pomicanje kista ne treba ništa vremena. Boje označavamo malim slovima engleske abecede. Na primjer, ako je zadan uzorak “aaabccccbbaab”, a Mirko odabere traku boje “a” kao početnu onda bojanje traje ukupno 12 sekundi te teče na sljedeći način:

Primijetite da ukupno vrijeme bojanja ovisi o boji početne trake. Odredite najmanje moguće ukupno vrijeme potrebno za bojanje trake u zadani uzorak.

Ulazni podaci

U prvom redu nalaze se prirodni broj n (n ≤ 100) — broj kvadratića na traci. U sljedećem redu nalazi se niz od n malih slova engleske abecede — zadani uzorak. Možete pretpostaviti da uzorak nije jednobojan.

Izlazni podaci

U prvi red ispišite traženo najmanje moguće vrijeme u sekundama.

Primjeri test podataka

ulaz

10
aaabbbcaaa

izlaz

6

ulaz

13
aaabccccbbaab

izlaz

12

ulaz

16
xxxxxxyayayayaya

izlaz

15