시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 70 | 22 | 17 | 26.562% |
Jaś jest robaczkiem i postanowił zamieszkać na drzewie. Drzewo, które wybrał jest bardzo młode - w momencie przeprowadzki Jasia ma tylko jeden wierzchołek ( oznaczony numerem 1 ).
Następnie zarówno drzewo jak i Jaś zajęli się swoimi sprawami. To znaczy:
Hektor obserwuje to wszystko i chciałby po każdym ruchu Jasia znać jego aktualną pozycję. Czy potrafisz mu pomóc?
W pierwszej linii znajduje się jedna liczba naturalna Z ( 1 <= Z <= 10 ) oznaczająca liczbę zestawów testowych. Następnie opisywane są kolejne zestawy.
W pierwszej linii zestawu znajduje się liczba naturalna N ( 1 <= N <= 106 ) oznaczająca liczbę wydarzeń.
W kolejnych N liniach podawane są opisy wydarzeń. Każdy z nich ma jedną z dwóch postaci o opisanym w treści znaczeniu:
Dla każdego zestawu należy wypisać tyle linii, ile razy na wejściu pojawiło się wydarzenie "J x". Dla każdego takiego wydarzenia należy wypisać numer wierzchołka, w którym znalazł się Jaś.
1 11 D 1 D 2 D 3 D 3 J 5 J 5 J 5 J 4 J 4 D 1 J 6
2 3 5 3 4 3
Na początku drzewo wypuszcza cztery nowe wierzchołki, ma więc ich w sumie 5. Pierwsze cztery wierzchołki są ze sobą połączone następująco 1-2-3-4. Piąty wierzchołek także przyłączany jest do wierzchołka numer 3.
Później przychodzi kolej na wędrówki Jasia. Pierwszy ruch wykonywany jest w stronę piątego wierzchołka, Jaś przemieszcza się więc do wierzchołka nr 2. Kolejne dwa ruchy w stronę piątego wierzchołka powodują, że Jaś kolejno trafia do wierzchołków 3 i wreszcie 5. Następne dwa ruchy wykonywane są w stronę wierzchołka 4 - Jaś musi cofnąć się do wierzchołka 3, aby tam trafić.
Wreszcie drzewo wypuszcza szósty wierzchołek przyłączony do pierwszego wierzchołka. Jaś przesuwa się w tamtą stronę, a więc w górę drzewa, do wierzchołka nr 3.
Contest > Spot > FallSpot 2010 3-2번