In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you are familiar with IRC chat, the support team is also reachable on PIRC network (irc.pirc.pl
) in #szkopul
channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
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ć.
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.
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.
Dla danych wejściowych:
10 BAACBBAAAC
poprawną odpowiedzią jest:
3
Autor zadania: Jakub Łącki.