Problem A - Pułapka na myszy
Problem B - Drzewo rozpinające
Problem C - Manipulowanie tablicą
Problem D - Figury wpisane
Problem E - Słownik danych
Problem F - Domki z pni
Problem G - Binarne drzewa gry
Problem H - Mnożenie wielomianów

 


 

 

1983

Problem G - Binarne drzewa gry


Opis

Binarne drzewo gry (ang. binary game tree) jest drzewem binarnym, w którym każdy węzeł posiada albo 0, albo 2 potomków. Każdy liść drzewa (węzeł bez potomków) ma skojarzone ze sobą dane. Dwóch potomków dowolnego węzła wewnętrznego reprezentuje wynik wykonania lub niewykonania określonego ruchu, a wartość w liściu drzewa jest miarą przydatności w zwycięstwie ruchów wzdłuż ścieżki prowadzącej od korzenia do tego liścia. Drzewo przedstawia ruchy dla dwóch graczy; korzeń oraz wszystkie węzły o parzystej odległości od korzenia (odległość wyrażana jest na drzewie liczbą krawędzi, po których należy przejść, aby dojść od korzenia do wybranego węzła) są ruchami do wyboru przez gracza A, natomiast węzły o odległości nieparzystej od korzenia są ruchami dla gracza B. Poniżej przedstawiono przykład:

 

 

Gracz A stara się zmaksymalizować wartość wybranych ruchów, natomiast gracz B stara się zminimalizować korzyści gracza A przez wybieranie ścieżki o niższej wartości.  W dowolnym węźle reprezentującym wybór dla A gracz A wybierze wartość wyższą, a w dowolnym węźle reprezentującym wybór dla B gracz B wybierze wartość niższą. W ten sposób wartością drzewa wewnętrznego jest albo wartość maksymalna, albo minimalna jego poddrzew w zależności o tego, czy pierwotne poddrzewo jest odpowiednio dla gracza A lub B.

Dla przykładowego drzewa gry mamy:

 

 

Danymi wejściowymi dla twojego programu będą opisy kilku binarnych drzew gry. Masz określić wartość (dla A) każdego drzewa Na wyjściu ma się pojawić jedynie wartość drzewa, nie musisz drukować drzewa w całości. Drzewo będzie posiadało co najwyżej 15 węzłów.

 

Specyfikacja wejścia

Dane dla tego problemu są ułożone w zestawach w pliku in.txt. Każdy zestaw może zawierać od jednego do 15 wierszy z danymi; pierwszy wiersz opisuje korzeń drzewa (węzeł numer 1), a każdy kolejny wiersz opisuje następny węzeł o wyższym numerze. Każdy wiersz będzie zawierał trzy liczby:

 

n - numer węzła dla lewego potomka (1 ≤ n 20)
m - numer węzła dla prawego potomka (1 ≤ m 20)
Powyższe dwie liczby przyjmują wartość 0, jeśli węzeł jest liściem
v - wartość liścia (-99 ≤ v ≤ 99) lub zero, jeśli węzeł nie jest liściem.

 

Każdy zestaw kończy się wierszem, w którym lewy potomek ma numer -1, a pozostałe dwie wartości przyjmują 0.

Dane wejściowe kończą się wraz z plikiem.

 

Specyfikacja wyjścia

Dla każdego zestawu danych należy podać wartość drzewa.

 

Przykładowe dane wejściowe

  2   3   0
  4   5   0
  6   7   0
  0   0   6
  0   0   3
  0   0   0        (Zauważ, że węzeł nr 6 nie jest używany)
  0   0  -5
  0   0  -2
  0   0   1
  0   0   0        (Węzeł nr 10 też nie jest używany)
  8   9   0
 -1   0   0        (Koniec zestawu)
 

Przykładowe dane wyjściowe

3

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.