ხის კოდი

დროის ლიმიტი: 1 წმ

მეხსიერების ლიმიტი: 64 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: პოლონეთი, ოლიმპიადა 7, ეტაპი 1


ორობითი ხე შეიძლება იყოს ცარიელი, ან შედგებოდეს ისეთი წვეროებისგან, რომელზედაც ორი ხეა დამაგრებული, ე.წ. მარცხენა და მარჯვენა ქვეხე. ხის თითოეულ წვეროზე ინგლისური ანბანის თითო სიმბოლო წერია.  ხის ყველაზე მაღალ წვეროს , რომელიც არ არის ქვეხე ეძახიან root -ს. ჩვენ ვამბობთ რომ ხე არის ორობითი ძებნის ხე (ე.წ BST) თუ ყველა წვეროსთვის სრულდება პირობა, რომელიც თითოეული წვეროსათვის აკმაყოფილებს პირობას: მარცხენა ქვეხის ყველა სიმბოლო ანბანში გვხვდება უფრო ადრე, ვიდრე მოცემულ წვეროზე დაწერილი სიმბოლო, ხოლო მარჯვენა ქვეხის ყველა სიმბოლო გვხვდება უფრო გვიან.

ორობითი ძებნის ხის კოდი არის შემდეგი:

     ცარიელი სტრინგი (0 ელემენტი) , როცა ხე არის ცარიელი.(ანუ ხე თუ ცარიელია კოდი არის “”)

     ასოების სტრინგი იწყება root-ის(სათავის)  სიმბოლოთი, მას მოსდევს მარცხენა ქვეხე , შემდეგ მარჯვენა ქვეხე.

განვიხილოთ ყველა k ცალი  BST ხე, რომელსაც ინგლისური ანბანის საწყისი ასოები აქვს ტოპებში. წარმოიდგინეთ ამ ხეების კოდების სია, რომლებიც ჩამოთვლილია ანბანის მიხედვით. (n, k) კოდს ამ სიაში ეწოდება მე-n-ე კოდი.

დაწერე პროგრამა რომელიც:

      წაიკითხავს  n და k რიცხვებს.

      გამოთვლის  (n  k ) კოდს.

 

      ჩაწერს პასუხს სტანდარტულ აუთფუთში

მაგალითი

 აქ არის ზუსტად 14 4 - ორობითი ძებნის ხის წვეროების კოდი (დალაგებული ალფაბეტით)

abcd abdc acbd adbc adcb bacd badc cabd cbad dabc dacb care dcab dcba

badc არის (7 , 4) -> (ანუ ამ 14 ელემენტიდან მეშვიდე არის badc) .

 

შესატანი მონაცემები: პირველი და ერთადერთი ხაზი ინფუთის არის 2 დადებითი ინტეჯერი n და k. გაყოფილები არიან ერთი space ით (1<=k<=19) . რიცხვი n არ აღემატება BST ხის კოდის რიცხვს, რომელიც k ცალი წვეროსგან მიიღება.

გამოსატანი მონაცემები: პირველ და ერთადერთ ხაზზე უნდა იყოს output სიტყვა ,  რომელიც იქნება lowercase ასოები ინგლისური ალფაბეტის და არის (n , k) კოდი.




მაგალითები

შესატანი მონაცემები
11 4 დაკოპირება
გამოსატანი მონაცემები
dacb დაკოპირება