Spinacze [B]

Limit pamięci: 64 MB

Mały Bajtosmoczek znalazł sobie świetną zabawę - robienie łańcuchów ze spinaczy. Zrobił więc sobie taki długi, długi łańcuch ze spinaczy Taty, zostawił go na stole i poszedł do szkoły. Niestety pech chciał, że Tata potrzebuje teraz wszystkich spinaczy, bynajmniej nie takich spiętych w łańcuch, lecz pojedynczych. Jednak zanim się zabierze za niszczenie łańcucha, chciałby wiedzieć, jak dużo czasu musi mu to zająć.

Tata będzie rozplątywał łańcuch, wykonując ruchy polegające na obróceniu jednego spinacza o wokół osi prostopadłej do powierzchni stołu. Każdy taki ruch zajmuje Tacie jedną sekundę. Na poniższym rysunku można zobaczyć efekt wykonania kilku ruchów na przykładowym łańcuchu spinaczy.

Rysunek 1: Kilka pierwszych kroków procesu rozplątywania łańcucha.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia opis łańcucha pozostawionego przez Bajtosmoczka,
• obliczy minimalną liczbę ruchów potrzebną do podzielenia łańcucha na pojedyncze spinacze,
• wypisze wynik na standardowe wyjście.

Wejście

Łańcuch jest opisany przez podanie ustawienia kolejnych jego ogniw oraz sposobów połączenia każdych dwóch kolejnych. Patrząc z góry na spinacz leżący na stole, możemy go zobaczyć w jednej z czterech pozycji tak, jak na poniższym rysunku.

(A)	(B)	(C)	(D)

Dwa spinacze mogą być połączone na jeden z dwóch sposobów: albo tak, że górna część lewego spinacza przechodzi pod górną częścią prawego spinacza, albo na odwrót. Obie sytuacje są zilustrowane na poniższym rysunku.

(P)	(Q)

W pierwszym wierszu standardowego wejścia znajduje się liczba () oznaczająca liczbę spinaczy. W drugim wierszu znajduje się opis łańcucha składający się na przemian z liter A, B, C lub D oraz P lub Q. Litery wskazują ułożenie kolejnych spinaczy oraz sposób połączenia kolejnych par spinaczy.

Wyjście

Na standardowe wyjście Twój program powinien zapisać jedną liczbę - minimalną liczbę ruchów potrzebnych do podzielenia łańcucha na pojedyncze ogniwa.

Przykład

Dla danych wejściowych:

5
CPBQAPAPB

poprawną odpowiedzią jest:

4

W powyższym przykładzie początkowy łańcuch wygląda tak samo, jak na rysunku 1. Można go rozplątać w czterech ruchach, jeśli się będzie postępować inaczej, niż jest to pokazane na tym rysunku.

Autor zadania: Szymon Acedański.