Runda 3 [Hard] - Kokosy

05.12.2010 - Damian Rusak
TrudnośćTrudność

 

Zadanie tygodnia

Runda 3; kategoria Hard

Limit czasowy: 1s; Limit pamięciowy: 32MB


Kokosy

W dzikiej dżungli na jednej z odległych wysp na oceanie żyje Małpa. Małpa to przebiegły wielbiciel lokalnych kokosów, które można zebrać z porastających wyspę palm. Jednak jest dla Małpy pewna rzecz, ważniejsza nawet od posiadania kokosów - to pragnienie, aby inne małpy tych kokosów nie miały. Innymi słowy Małpa jest zwierzęcym socjopatą. Małpa dowiedział się, że pozostałe osobniki jego gatunku wybierają się w okolicę wielkiego wulkanu w centrum wyspy, aby oddać cześć przodkom. Postanowił wykorzystać tę okazję, aby ogołocić z kokosów lokalne zbiorowisko palm.

Palmy rosną na grząskim piasku i dlatego Małpa może wspinać się na nie tylko po lianach, które łączą niektóre palmy ze sobą, bądź wspiąć się na jedyną palmę, która rośnie na twardym podłożu. Ale co za niespodzianka! "Lianowe" połączenia między palmami tworzą "drzewo" - z każdej palmy można dojść do każdej (być może po drodze poprzez inne palmy) przechodząc po lianach, ale można to zrobić jedynie na jeden sposób. Ponadto wiadomo, że z żadna palma nie jest połączona z więcej niż czterema innymi.

Małpa wie, że przejście po każdej lianie jest męczące - musi przed jej przebyciem spożyć jednego kokosa dla wzmocnienia sił, inaczej nie może po niej przejść. Ponadto każda palma obrodziła w tym sezonie w niewielką liczbą kokosów - na każdej z nich rośną jeden, dwa lub trzy kokosy. Małpa zastanawia się, jak zebrać wszystkie kokosy i wrócić na ziemię przez palmę rosnącą na twardym podłożu, jeżeli z owej palmy wystartuje. Wie jedynie, że to możliwe, bo kiedyś jego wujkowi ta sztuka się udała.

Małpa zbiera kokosy z palmy, gdy wejdzie na nią po raz pierwszy. Musi jednak najpierw spożyć kokosa na przejście liany, dopiero potem może po owej lianie przejść. Kokosy z palmy, z której Małpa zaczyna, są zbierane przez niego od razu.

Wejście:

Pierwsza linia wejścia zawiera jedną liczbę naturalną $ n $ - liczbę palm ($ 1 \leq n \leq 10^{5} $). Palmy numerowane są od $ 1 $ do $ n $, przy czym palma o numerze $ 1 $ to palma, z której rozpocząć się ma i na której ma się skończyć podróż Małpy. W kolejnej linii znajduje się $ n $ liczb ze zbioru $ \left\{1,2,3\right\} $ - kolejno liczba kokosów na kolejnych palmach (pierwsza liczba dotyczy palmy nr 1, druga palmy nr 2 itd.). W kolejnych $ n-1 $ liniach znajdują się pary liczb $ a_{i} $ $ b_{i} $ oznaczające, że palmy o tych numerach połączone są lianą. Żadna palma nie pojawi się w więcej niż czterech parach.

Wyjście:

Pierwsza linia wejścia powinna zawierać jedną liczbę całkowitą $ k $ - długość ciągu kolejnych przebywanych przez Małpę palm. W kolejnej linii winno znajdować się $ k $ liczb - numerów kolejnych palm, które przebywać powinien Małpa, aby nigdy po drodze nie zabrakło mu kokosów i zebrał wszystkie. Ciąg powinien kończyć i zaczynać się liczbą $ 1 $. Jeśli istnieje wiele rozwiązań, Twój program powinien wypisać dowolne z nich.

Przykład:

Wejście:

5
2 2 3 1 1
1 3
3 4
3 5
1 2

Wyjście:

9
1 3 4 3 5 3 1 2 1

Wyjaśnienie:

Poniższa ilustracja obrazuje jak Małpa chodzi po palmach i jego kokosowy stan posiadania:

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
PozycjaImię i nazwiskoWynikCzasKokosy
1Piotr Bejda1006:17:3510
2Tomasz Gieniusz1007:02:5210
3Tomasz Richert1011:43:3410
4Kuba Skałecki1011:58:0110
5Krzysztof Drab1036:25:4610
6Witold Długosz1037:42:2210
7Marcin Skiba1057:48:3510
8Damian Straszak10109:17:4910
9Łukasz Hanuszczak10111:01:1910
10Przemysław Derengowski10127:19:3110
11Maciej Kisiel10156:31:3110
12Bartek Dudek10159:33:4610
13Krzysztof Trzepla10181:44:0910
14Jakub Kołodziej10491:57:1510
15Adam Czapliński510:16:065
16Arek Wróbel584:46:105
17Przemek Komosa410:18:424
18Maciej Szeptuch4150:48:454
19Krzysztof Cirocki4157:46:424
5
Twoja ocena: Brak Ocena: 5 (1 ocena)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com