SHARE
TWEET

Untitled

a guest Apr 19th, 2014 386 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2.  
  3. ZADANIE
  4.  
  5. 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.
  6.  
  7.  
  8.  
  9. 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.
  10.  
  11.  
  12.  
  13. WEJŚCIE
  14.  
  15. 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:
  16.  
  17.  - liczba całkowita - etykieta wierzchołka,
  18.  
  19.  - znak odstępu  (kod ASCII 32),
  20.  
  21.  - 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.
  22.  
  23.  
  24.  
  25. WYJŚCIE
  26.  
  27. Wiersz zawierający dwie liczby całkowite będące rozwiązaniem postawionego problemu oddzielone znakiem odstępu.
  28.  
  29.  
  30.  
  31. OGRANICZENIA
  32.  
  33. 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.
  34.  
  35.  
  36.  
  37. LIMITY
  38.  
  39. 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ą.
  40.  
  41.  
  42.  
  43. PRZYKŁAD 1
  44.  
  45. wejście:
  46.  
  47. 3 LL
  48.  
  49. 5
  50.  
  51. -8 R
  52.  
  53. 1 L
  54.  
  55. -2 LR
  56.  
  57. wyjście:
  58.  
  59. -3 9
  60.  
  61.  
  62. /*
  63.  
  64. KOMENTARZ DO ROZWIĄZANIA
  65.  
  66.  
  67. Konstrukcja drzewa binarnego:
  68.  
  69.  
  70.     5
  71.  
  72.    / \
  73.  
  74.   1  -8
  75.  
  76.  / \
  77.  
  78. 3  -2
  79.  
  80.  
  81. 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.
  82.  
  83. */
  84.  
  85.  
  86.  
  87. PRZYKŁAD 2
  88.  
  89. wejście:
  90.  
  91. 8 L
  92.  
  93. -5 LL
  94.  
  95. 8 LLR
  96.  
  97. -8 LRR
  98.  
  99. 2 LR
  100.  
  101. -9 LLL
  102.  
  103. -3 LRL
  104.  
  105. 6 RR
  106.  
  107. 2
  108.  
  109. -8 R
  110.  
  111. wyjście:
  112.  
  113. -4 13
  114.  
  115.  
  116.  
  117. PRZYKŁAD 3
  118.  
  119. wejście:
  120.  
  121. -82 LRL
  122.  
  123. 80 L
  124.  
  125. -63
  126.  
  127. -92 LRLR
  128.  
  129. -63 RLRL
  130.  
  131. 51 RR
  132.  
  133. -95 RRLR
  134.  
  135. 67 RRRLR
  136.  
  137. -73 RLLL
  138.  
  139. 29 RLR
  140.  
  141. -49 RRL
  142.  
  143. -27 RLL
  144.  
  145. 73 LR
  146.  
  147. 39 RRRL
  148.  
  149. -42 RL
  150.  
  151. -29 LL
  152.  
  153. -25 RLRR
  154.  
  155. -77 RLLR
  156.  
  157. -88 LLR
  158.  
  159. 4 RRR
  160.  
  161. 3 RRLLR
  162.  
  163. -64 RRLL
  164.  
  165. -80 R
  166.  
  167. -85 LLRR
  168.  
  169. 38 LLL
  170.  
  171. wyjście:
  172.  
  173. -289 26
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top