Zakręty [A]
Limit pamięci: 128 MB
Bajtazar wybrał się na wycieczkę samochodową po krętej, górskiej drodze.
Roztropnie wziął ze sobą mapę, jednakże zupełnie nie jest w stanie
określić, w którym miejscu mapy się aktualnie znajduje.
Ilustracja drogi na mapie zawiera zakrętów, z których każdy
jest o w lewo lub w prawo.
Dla uproszczenia możemy reprezentować całą mapę przez -literowy
napis złożony z liter L i/lub P.
Zakładając, że Bajtazar ma właśnie przed sobą -ty zakręt na drodze
(choć może tego nie wiedzieć), przez oznaczamy liczbę zakrętów, które
Bajtazar musi pokonać, żeby być pewnym, w którym miejscu mapy się znajduje.
Znaczenie wartości najlepiej jest rozważyć na przykładzie.
Załóżmy, że droga jest reprezentowana przez napis LLPPLPL.
Jeśli Bajtazar ma przed sobą aktualnie drugi zakręt, to przed
przejechaniem tego zakrętu wie, że znajduje się przed jednym z zakrętów: , , albo
(gdyż widzi przed sobą zakręt w lewo).
Po pokonaniu jednego zakrętu (L) Bajtazar widzi przed sobą trzeci zakręt drogi
- P,
co oznacza, że początkowo nie mógł się on znajdować przed pierwszym zakrętem
(gdyż następny byłby w lewo) ani przed ostatnim zakrętem (gdyż po jego pokonaniu
zobaczyłby koniec drogi).
Wie on zatem, że aktualnie znajduje się przed trzecim lub szóstym zakrętem na mapie.
Pokonanie kolejnego zakrętu spowoduje, że Bajtazar zobaczy przed
sobą zakręt P, co oznacza, że w chwili początkowej nie mógł się on znajdować
tuż przed piątym zakrętem, gdyż w takim wypadku zobaczyłby w tym momencie zakręt w lewo.
Ostatecznie pokonanie dwóch zakrętów upewnia Bajtazara, że znajduje się
on przed czwartym zakrętem na drodze, a zatem .
Zadanie
Napisz program, który:
- wczyta ze standardowego wejścia opis drogi,
- wyznaczy wartości dla ,
- wypisze wynik na standardowe wyjście.
Wejście
Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą
().
Drugi wiersz zawiera opis drogi w postaci ciągu liter L i/lub P, bez
jakichkolwiek odstępów.
Wyjście
Wyjście powinno zawierać dokładnie wierszy. W -tym z nich powinna znajdować się
liczba .
Przykład
Dla danych wejściowych:
7
LLPPLPL
poprawną odpowiedzią jest:
1
2
1
2
2
2
1
Autor zadania: Marek Cygan.