Loteria [B]
Limit pamięci: 128 MB
Przedsiębiorstwo Bajtocki Lotek specjalizuje się w przeprowadzaniu gier liczbowych
i loterii pieniężnych, wśród których największą popularnością cieszy się
loteria o nazwie Gra w litery.
Również Bajtazar postanowił spróbować szczęścia w grze.
Kupon do Gry w litery zawiera pozycji.
Na każdej z nich można zakreślić jedną z trzech liter: A, B lub C.
Poniższy rysunek przedstawia przykładowe wypełnienie kuponu dla :
Losowanie zwycięzców przeprowadza się przy pomocy maszyny losującej, w której
znajduje się metalowych kulek
trzech rodzajów: kulek z literą A, z literą B i z literą C.
W górnej części maszyny jest rozmieszczonych równomiernie otworów o średnicy mniejszej
niż średnica kulki.
W pewnym momencie losowania włączany jest mechanizm pneumatyczny, który powoduje, że
do każdego z otworów przyssana zostaje jedna kulka.
Wypisując kolejno litery znajdujące się na wylosowanych kulkach, otrzymuje się
ciąg złożony z liter, stanowiący wynik losowania.
Szczęśliwi właściciele kuponów, na których zakreślono taki właśnie ciąg liter,
zdobywają nagrodę główną - milion bajtalarów do podziału.
Na rysunku przedstawiono wynik losowania, przy którym powyższy kupon uzyskałby główną nagrodę.
Bajtazar nabył kupon i zakreślił na nim liter.
Zanim jednak zdążył złożyć swój kupon w kolekturze, w mediach pojawił
się przeciek, że losowanie w Grze w litery nie jest do końca uczciwe.
Zbadano bowiem, że kulki tego samego rodzaju - czyli z tą samą literą -
odpychają się i nigdy nie ustawią się przy sąsiednich otworach
w trakcie losowania (np. układ kulek przedstawiony na powyższym rysunku nie byłby możliwy).
Bajtazar, dowiedziawszy się o tym, postanowił zmienić ciąg liter, który wskazał,
tak aby żadne dwie kolejne litery w ciągu nie były takie same.
Żeby nie kusić losu, chciałby zmienić możliwie najmniej liter w swoim ciągu.
Pomóż Bajtazarowi ustalić, ile liter musi zmienić.
Wejście
Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą ().
Drugi wiersz zawiera ciąg złożony z znaków A, B i/lub C.
W ciągu tym występuje co najmniej jedna para sąsiadujących ze sobą takich samych liter.
Wyjście
Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę całkowitą dodatnią -
minimalną liczbę liter w ciągu, które trzeba zmienić, tak aby żadne dwie takie same
litery nie występowały w nim obok siebie.
Przykład
Dla danych wejściowych:
10
BAACBBAAAC
poprawną odpowiedzią jest:
3
Autor zadania: Jakub Łącki.