Zadanie tygodnia
Runda 3; kategoria Hard
Limit czasowy: 1s; Limit pamięciowy: 32MB
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ą - liczbę palm (). Palmy numerowane są od do , przy czym palma o numerze to palma, z której rozpocząć się ma i na której ma się skończyć podróż Małpy. W kolejnej linii znajduje się liczb ze zbioru - kolejno liczba kokosów na kolejnych palmach (pierwsza liczba dotyczy palmy nr 1, druga palmy nr 2 itd.). W kolejnych liniach znajdują się pary liczb 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ą - długość ciągu kolejnych przebywanych przez Małpę palm. W kolejnej linii winno znajdować się 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ą . Jeśli istnieje wiele rozwiązań, Twój program powinien wypisać dowolne z nich.
Przykład:
Wejście:
Wyjście:
Wyjaśnienie:
Poniższa ilustracja obrazuje jak Małpa chodzi po palmach i jego kokosowy stan posiadania:
Pozycja | Imię i nazwisko | Wynik | Czas | Kokosy |
---|---|---|---|---|
1 | Piotr Bejda [3] | 10 | 06:17:35 | 10 |
2 | Tomasz Gieniusz [4] | 10 | 07:02:52 | 10 |
3 | Tomasz Richert [5] | 10 | 11:43:34 | 10 |
4 | Kuba Skałecki [6] | 10 | 11:58:01 | 10 |
5 | Krzysztof Drab [7] | 10 | 36:25:46 | 10 |
6 | Witold Długosz [8] | 10 | 37:42:22 | 10 |
7 | Marcin Skiba [9] | 10 | 57:48:35 | 10 |
8 | Damian Straszak [10] | 10 | 109:17:49 | 10 |
9 | Łukasz Hanuszczak [11] | 10 | 111:01:19 | 10 |
10 | Przemysław Derengowski [12] | 10 | 127:19:31 | 10 |
11 | Maciej Kisiel [13] | 10 | 156:31:31 | 10 |
12 | Bartek Dudek [14] | 10 | 159:33:46 | 10 |
13 | Krzysztof Trzepla [15] | 10 | 181:44:09 | 10 |
14 | Jakub Kołodziej [16] | 10 | 491:57:15 | 10 |
15 | Adam Czapliński [17] | 5 | 10:16:06 | 5 |
16 | Arek Wróbel [18] | 5 | 84:46:10 | 5 |
17 | Przemek Komosa [19] | 4 | 10:18:42 | 4 |
18 | Maciej Szeptuch [20] | 4 | 150:48:45 | 4 |
19 | Krzysztof Cirocki [21] | 4 | 157:46:42 | 4 |
Odnośniki:
[1] http://informatyka.wroc.pl/user
[2] http://informatyka.wroc.pl/user/register
[3] http://informatyka.wroc.pl/user/1612
[4] http://informatyka.wroc.pl/user/2102
[5] http://informatyka.wroc.pl/user/1616
[6] http://informatyka.wroc.pl/user/1682
[7] http://informatyka.wroc.pl/user/600
[8] http://informatyka.wroc.pl/user/2175
[9] http://informatyka.wroc.pl/user/819
[10] http://informatyka.wroc.pl/user/2093
[11] http://informatyka.wroc.pl/user/126
[12] http://informatyka.wroc.pl/user/462
[13] http://informatyka.wroc.pl/user/792
[14] http://informatyka.wroc.pl/user/334
[15] http://informatyka.wroc.pl/user/1009
[16] http://informatyka.wroc.pl/user/1717
[17] http://informatyka.wroc.pl/user/531
[18] http://informatyka.wroc.pl/user/424
[19] http://informatyka.wroc.pl/user/2060
[20] http://informatyka.wroc.pl/user/113
[21] http://informatyka.wroc.pl/user/1510