Tańce gordyjskie Krzyśków
Limit pamięci: 32 MB
Na zakończenie tegorocznej edycji Pogromców Algorytmów
Krzyśki odpowiedzialne za prawidłowy przebieg zawodowów
(KC, KD, KO, KS)
postanowili odtańczyć radosny taniec gordyjski.
Taniec gordyjski to tradycyjny bajtocki taniec tańczony przez
dwie pary tancerzy.
Początkowo tancerze stoją w wierzchołkach kwadratu ,
w dwóch parach: i .
Każda z par rozciąga między sobą sznurek.
Tak więc na początku oba sznurki są rozciągnięte poziomo i
równolegle do siebie.
Taniec składa się z ciągu ruchów, z których każdy
może być ruchem następującego rodzaju:
-
Tancerze stojący w punktach i zamieniają się
miejscami (nie puszczając swoich sznurków) w ten sposób, że
tancerz stojący w punkcie podnosi rękę ze sznurkiem do góry
i idąc do punktu przepuszcza tancerza idącego z punktu
do przed sobą, pod swoją ręką.
-
Wszyscy tancerze wykonują obrót o 90 stopni w prawo nie puszczając
sznurków, czyli tancerz, który stał w punkcie idzie do punktu
,
ten, który stał w punkcie idzie do punktu , ten, który stał
w punkcie idzie do punktu , a ten, który stał
w punkcie
idzie do punktu .
W trakcie tańca sznurki plączą się ze sobą, jednak na koniec tańca
powinny zostać rozplątane i znowu być rozciągnięte poziomo i
równolegle do siebie.
Tancerze nie muszą przy tym stać na tych samych miejscach, na których
stali na początku.
Taniec ten wymaga od tancerzy dużej wprawy, gdyż w trakcie tańca
sznurki mogą być bardzo splątane i ciąg ruchów, który prowadziłby
do ich rozplątania i rozciągnięcia poziomo i równolegle do siebie
może być trudny do odgadnięcia.
Krzyśki to początkujący tancerze.
Twoje zadanie polega na napisaniu programu, który pomógłby im
zakończyć rozpoczęty taniec.
Na podstawie ciągu już wykonanych ruchów Twój program powinien wyznaczyć
minimalną liczbę ruchów pozwalających zakończyć taniec.
Przykład
Przykładowo, po wykonaniu ciągu ruchów otrzymujemy
następującą konfigurację:
Najkrótszy ciąg ruchów, który pozwala zakończyć taniec ma długość
5 i jest nim .
Zadanie
Napisz program, który:
- wczyta ze standardowego wejścia opis ciągu wykonanych ruchów w tańcu,
- wyznaczy minimalną liczbę ruchów potrzebnych do rozplątania
sznurków i rozciągnięcia ich poziomo i równolegle do siebie
(po wykonaniu tych ruchów tancerze nie muszą znajdować się
na swoich początkowych pozycjach),
- wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu standardowego wejścia zapisana jest jedna
dodatnia liczba całkowita równa liczbie wykonanych ruchów,
.
W drugim wierszu zapisane jest jedno słowo długości
złożone z liter i/lub .
Kolejne litery tego słowa reprezentują kolejno wykonane
ruchy w tańcu.
Wyjście
Twój program powinien wypisać na standardowe wyjście,
w pierwszym i jedynym wierszu, jedną liczbę całkowitą -
minimalną liczbę ruchów ( i/lub ) koniecznych do
rozplątania sznurków i rozciągnięcia ich poziomo i równolegle do siebie.
Przykład
Dla danych wejściowych:
2
SS
poprawną odpowiedzią jest:
5
Autor zadania: Piotr Chrząstowski.