Guest User

Untitled

a guest
Dec 6th, 2015
107
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. ZADANIE
  2.  
  3. Rozważmy niepuste drzewo binarne T etykietowane literami alfabetu angielskiego (tylko małe litery) 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.
  4.  
  5. Wyznacz najstarsze leksykograficznie słowo, jakie można zbudować z etykiet wierzchołków rozważanego drzewa występujących na dowolnej ścieżce wierzchołek zewnętrzny (liść) drzewa T - korzeń drzewa T.
  6.  
  7.  
  8.  
  9. WEJŚCIE
  10.  
  11. 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:
  12.  
  13. - małą literę alfabetu angielskiego (kod ASCII od 97 do 122) - etykieta wierzchołka,
  14.  
  15. - znak odstępu (kod ASCII 32),
  16.  
  17. - 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.
  18.  
  19.  
  20.  
  21. WYJŚCIE
  22.  
  23. Wiersz zawierajacy ciąg znaków będący rozwiązaniem postawionego problemu.
  24.  
  25.  
  26.  
  27. OGRANICZENIA
  28.  
  29. Liczba wierzchołków drzewa T nie większa niż 10^7. Wysokość drzewa T ograniczona przez 2^6.
  30.  
  31.  
  32.  
  33. LIMITY
  34.  
  35. Złożoność czasowa O(n), złożoność pamięciowa O(n), gdzie n jest liczbą wierzchołków drzewa T.
  36.  
  37.  
  38.  
  39. PRZYKŁAD 1
  40.  
  41. wejście:
  42.  
  43. a LL
  44. d
  45. a R
  46. s L
  47.  
  48. wyjście:
  49.  
  50. asd
  51.  
  52. /* KOMENTARZ DO ROZWIĄZANIA
  53.  
  54.  
  55.  
  56.  
  57. Konstrukcja drzewa binarnego:
  58.  
  59.  
  60.  
  61.  
  62.  
  63.  
  64. d
  65.  
  66.  
  67.  
  68.  
  69. / \
  70.  
  71.  
  72.  
  73.  
  74. s a
  75.  
  76.  
  77.  
  78.  
  79. /
  80.  
  81.  
  82.  
  83.  
  84. a
  85.  
  86.  
  87.  
  88.  
  89.  
  90.  
  91. Możliwe słowa na ścieżce liść drzewa – korzeń drzewa to asd i ad. Leksykograficznie większe jest słowo asd. */
  92.  
  93.  
  94.  
  95. PRZYKŁAD 2
  96.  
  97. wejście:
  98.  
  99. s LR
  100. o LRR
  101. m RR
  102. p LRLRL
  103. k
  104. w LRL
  105. a LL
  106. t L
  107. h R
  108. j LRLR
  109.  
  110. wyjście:
  111.  
  112. pjwstk
  113.  
  114.  
  115.  
  116. PRZYKŁAD 3
  117.  
  118. wejście:
  119.  
  120. w RLR
  121.  
  122.  
  123. t LLR
  124.  
  125.  
  126. m LLRR
  127.  
  128.  
  129. f LRLLL
  130.  
  131.  
  132. h LRR
  133.  
  134.  
  135. n L
  136.  
  137.  
  138. g LLL
  139.  
  140.  
  141. v RLL
  142.  
  143.  
  144. n RLLR
  145.  
  146.  
  147. r RLLRR
  148.  
  149.  
  150. k RLRR
  151.  
  152.  
  153. k LR
  154.  
  155.  
  156. i
  157.  
  158.  
  159. f LRLL
  160.  
  161.  
  162. z RLLL
  163.  
  164.  
  165. y RRLL
  166.  
  167.  
  168. i RRLLL
  169.  
  170.  
  171. v RRR
  172.  
  173.  
  174. z RRRL
  175.  
  176.  
  177. n LLLL
  178.  
  179.  
  180. w LLRRL
  181.  
  182.  
  183. r RR
  184.  
  185.  
  186. z R
  187.  
  188.  
  189. t RLLLL
  190.  
  191.  
  192. w RRLR
  193.  
  194.  
  195. s LRL
  196.  
  197.  
  198. f RLLRRR
  199.  
  200.  
  201. e RRRR
  202.  
  203.  
  204. j RLLLR
  205.  
  206.  
  207. u RRL
  208.  
  209.  
  210. v LL
  211.  
  212.  
  213. l RRRLL
  214.  
  215.  
  216. p LRLLR
  217.  
  218.  
  219. o RL
  220.  
  221. wyjście:
  222.  
  223. wurzi
  224.  
  225.  
  226.  
  227. Source code size limit 50000
  228. Available languages ADA 95 (gnat 4.3.2) Any document (no testing) Assembler (nasm 2.03.01) Bash (bash-4.0.37) Brainf**k (bff 1.0.3.1) C (gcc 4.3.2) C# (gmcs 2.0.1) C++ (g++ 4.3.2) C++ (g++ 4.0.0-8) C99 strict (gcc 4.3.2) Clips (clips 6.24) Clojure (clojure 1.1.0) Common Lisp (clisp 2.44.1) Common Lisp (sbcl 1.0.18) D (gdc 4.1.3) Erlang (erl 5.6.3) F# (fsharp 2.0.0) Fortran 95 (gfortran 4.3.2) Go (gc 2010-07-14) Haskell (ghc 6.10.4) Icon (iconc 9.4.3) Intercal (ick 0.28-4) JAR (JavaSE 6) Java (JavaSE 6) JavaScript (rhino 1.7R1-2) Lua (luac 5.1.3) Nemerle (ncc 0.9.3) Nice (nicec 0.9.6) Ocaml (ocamlopt 3.10.2) Pascal (gpc 20070904) Pascal (fpc 2.2.4) PDF (ghostscript 8.62) Perl (perl 5.12.1) Perl 6 (rakudo-2010.08) PHP (php 5.2.6) Pike (pike 7.6.112) PostScript (ghostscript 8.62) Prolog (swipl 5.6.58) Python (python 2.5) Python 3 (python 3.1.2) Ruby (ruby 1.9.0) Scala (scala 2.8.0) Scheme (stalin 0.11) Scheme (guile 1.8.5) Smalltalk (gst 3.0.3) Tcl (tclsh 8.5.3) TECS Text (plain text) Whitespace (wspace 0.3)
RAW Paste Data