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.
Ostatnio Bajtek zobaczył w Bajternecie drzewo bajnarne. Drzewem bajnarnym nazywamy dowolne ukorzenione drzewo, w którym każdy wierzchołek ma lub synów. Wysokością drzewa nazywamy liczbę wierzchołków na najdłuższej ścieżce od korzenia do pewnego z liści; drzewo puste ma wysokość 0. Na drzewach bajnarnych zdefiniowany jest porządek leksykograficzny. Drzewo jest leksykograficznie mniejsze od drzewa , gdy:
Jeśli dany wierzchołek nie posiada lewego syna, to jego lewe poddrzewo uznajemy za drzewo puste; analogicznie w przypadku braku prawego syna.
Jeśli drzewa i są różne i drzewo nie jest leksykograficznie mniejsze niż drzewo , to drzewo jest leksykograficznie większe niż drzewo .
Twoje zadanie polega na wczytaniu opisu drzewa i obliczeniu numeru tego drzewa w porządku leksykograficznym. Drzewo składające się z jednego wierzchołka ma numer .
W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita () będąca liczbą drzew. W kolejnych wierszach znajduje się opisów drzew. W pierwszym wierszu opisu drzewa znajduje się jedna liczba całkowita () będąca liczbą wierzchołków, z których składa się drzewo. Wierzchołki drzewa numerujemy liczbami od do , przy czym wierzchołek jest korzeniem. Kolejne wierszy opisuje krawędzie drzewa. -ty z nich zawiera dwie liczby całkowite i () będące numerami lewego i prawego syna wierzchołka . W przypadku gdy wierzchołek nie ma lewego syna, , a gdy nie ma prawego, .
Na standardowe wyjście należy wypisać dokładnie wierszy zawierających jedną liczbę całkowitą będącą numerem odpowiedniego drzewa w zadanym porządku modulo .
Dla danych wejściowych:
4 1 -1 -1 2 -1 2 -1 -1 2 2 -1 -1 -1 3 2 3 -1 -1 -1 -1
poprawną odpowiedzią jest:
1 2 3 4
Autorzy zadania: Bartosz Górski i Jakub Pawlewicz.