W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
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.
Napisz program, który:
Ł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.
Na standardowe wyjście Twój program powinien zapisać jedną liczbę - minimalną liczbę ruchów potrzebnych do podzielenia łańcucha na pojedyncze ogniwa.
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.