Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- ZADANIE
- Rozważmy niepuste drzewo binarne T etykietowane liczbami całkowitymi i zapisane wierzchołkowo tak, że pozycję dowolnego wierzchołka x w drzewie T określa ciąg skierowań krawędzi (L - lewa krawędź, R - prawa krawędź) jakie pokonamy przechodząc w tym drzewie ścieżkę od korzenia do wierzchołka x.
- Wyznacz kolejno minimalną oraz maksymalną możliwą sumę etykiet wierzchołków rozważanego drzewa występujących na dowolnej ścieżce wierzchołek zewnętrzny (liść) drzewa T - korzeń drzewa T.
- WEJŚCIE
- Ciąg wierszy zakończony symbolem znaku końca pliku (EOF) reprezentujący poprawnie (zgodnie z powyższym opisem) pewne drzewo binarne T. Każdy pojedynczy wiersz zakończony znakiem nowej linii (kod ASCII 10) opisujący pozycję wierzchołka w drzewie T i zawierający:
- - liczba całkowita - etykieta wierzchołka,
- - znak odstępu (kod ASCII 32),
- - ciąg znaków L (kod ASCII 76) oraz R (kod ASCII 82) - ciąg skierowań krawędzi na ścieżce od korzenia drzewa do rozważanego wierzchołka.
- WYJŚCIE
- Wiersz zawierający dwie liczby całkowite będące rozwiązaniem postawionego problemu oddzielone znakiem odstępu.
- OGRANICZENIA
- Liczba wierzchołków drzewa T nie większa niż 10^7. Wartości etykiety wierzchołków drzewa ograniczone odpowiednio przez -10^9 oraz 10^9. Wysokość h drzewa T ograniczona przez 2^6.
- LIMITY
- Złożoność czasowa O(hn), złożoność pamięciowa O(n), gdzie n jest liczbą wierzchołków drzewa T a h jest jego wysokością.
- PRZYKŁAD 1
- wejście:
- 3 LL
- 5
- -8 R
- 1 L
- -2 LR
- wyjście:
- -3 9
- /*
- KOMENTARZ DO ROZWIĄZANIA
- Konstrukcja drzewa binarnego:
- 5
- / \
- 1 -8
- / \
- 3 -2
- Możliwe sumy etykiet wierzchołków na ścieżce liść drzewa – korzeń drzewa to kolejno 3+1+5=9, (-2)+1+5=4 oraz (-8)+5=-3. Wartości minimalna i maksymalna w/w sum to -3 i 9.
- */
- PRZYKŁAD 2
- wejście:
- 8 L
- -5 LL
- 8 LLR
- -8 LRR
- 2 LR
- -9 LLL
- -3 LRL
- 6 RR
- 2
- -8 R
- wyjście:
- -4 13
- PRZYKŁAD 3
- wejście:
- -82 LRL
- 80 L
- -63
- -92 LRLR
- -63 RLRL
- 51 RR
- -95 RRLR
- 67 RRRLR
- -73 RLLL
- 29 RLR
- -49 RRL
- -27 RLL
- 73 LR
- 39 RRRL
- -42 RL
- -29 LL
- -25 RLRR
- -77 RLLR
- -88 LLR
- 4 RRR
- 3 RRLLR
- -64 RRLL
- -80 R
- -85 LLRR
- 38 LLL
- wyjście:
- -289 26
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement