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.
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 .
Napisz program, który:
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 powinno zawierać dokładnie wierszy. W -tym z nich powinna znajdować się liczba .
Dla danych wejściowych:
7 LLPPLPL
poprawną odpowiedzią jest:
1 2 1 2 2 2 1
Autor zadania: Marek Cygan.