English
Zobacz więcej:
- dla uczniów szkół podstawowych: oij.edu.pl/start/
- dla uczniów szkół średnich: oi.edu.pl/l/jak_zaczac/
Zadanie Spinacze (B) (spi)
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) |
Rysunek 2: Cztery możliwe ustawienia spinacza na stole.
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) |
Rysunek 3: Dwie możliwości spięcia spinaczy na przykładzie pary BA.
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.