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.
Grafem nazywamy każdą parę , w której jest skończonym zbiorem elementów zwanych wierzchołkami grafu, a jest podzbiorem zbioru wszystkich nieuporządkowanych par różnych wierzchołków. Elementy zbioru nazywamy krawędziami grafu. Jeżeli dla każdej pary różnych wierzchołków , istnieje dokładnie jeden ciąg różnych wierzchołków taki, że , oraz pary dla , to graf nazywamy drzewem. O wierzchołkach , mówi się, że są odległe w drzewie o .
Wiadomo, że drzewo o wierzchołkach ma dokładnie krawędzi. Drzewo , którego wierzchołki są ponumerowane od do , można jednoznacznie opisać, podając liczbę wierzchołków , a następnie odpowiedni ciąg par liczb naturalnych opisujący wszystkie jego krawędzie.
Dowolną permutację wierzchołków - to znaczy ciąg, w którym każdy wierzchołek drzewa występuje dokładnie jeden raz - nazywamy porządkiem obchodzenia drzewa. Jeżeli każde kolejne dwa wierzchołki w pewnym porządku są odległe w drzewie co najwyżej o , to mówimy, że jest to porządek obchodzenia drzewa ze skokiem .
Wiadomo, że dla każdego drzewa można wyznaczyć porządek jego obchodzenia ze skokiem .
Rysunek przedstawia drzewo o 7 wierzchołkach. Wierzchołki drzewa są reprezentowane przez czarne kropki, a krawędzie przez odcinki łączące kropki.
To drzewo można obejść ze skokiem 3 odwiedzając jego wierzchołki w następującym porządku: 7 2 3 5 6 4 1.
Ułóż program, który:
W kolejnych wierszach standardowego wyjścia należy zapisać numery kolejnych wierzchołków w porządku obchodzenia drzewa ze skokiem trzy - każdą liczbę należy zapisać w osobnym wierszu.
Dla danych wejściowych:
7 1 2 2 3 2 4 4 5 5 6 1 7
poprawną odpowiedzią jest:
7 2 3 5 6 4 1
Autor zadania: Krzysztof Diks.