İkitərəfli axtarış ağacının yaradılması
BDS (binar axtarış ağacı) axtarış üçün effektiv bir strukturdur. BDS-də sol alt ağacın bütün elementləri kök dəyərindən kiçik, sağ alt ağacın bütün elementləri isə böyükdür. BDS üçün bir nümunəyə baxaq:
Adətən BDS elementlərin ardıcıl daxil edilməsi ilə qurulur. Bu halda, elementlərin daxil edilmə ardıcıllığı nəticə ağacının strukturuna təsir edir. Məsələn:
Bu məsələdə sizdən 1 -dən n-ə qədər olan rəqəmlərin elə bir daxil edilmə ardıcıllığını tapmaq tələb olunur ki, alınan BDS-nin hündürlüyü h-dən böyük olmasın. BDS-nin hündürlüyü aşağıdakı kimi müəyyən edilir:
Heç bir zirvə içerməyən BDS-nin hündürlüyü 0-a bərabərdir.
Əks halda, BDS-nin hündürlüyü sol və sağ alt ağacların hündürlüklərinin maksimumuna 1 əlavə etməklə bərabərdir.
Məsələnin şərtlərinə bir neçə daxil edilmə ardıcıllığı uyğun gələ bilər. Bu halda, əvvəlcə kiçik rəqəmlərin olduğu ardıcıllığı çıxarmaq lazımdır. Məsələn, n = 4, h = 3 üçün 1 3 2 4 ardıcıllığını çıxarmaq lazımdır, 2 1 4 3 və ya 3 2 1 4 deyil.
Giriş verilənləri
Hər testdə iki natural ədəd n (1 ≤ n ≤ 10000) və h (1 ≤ h ≤ 30) verilir. Son test n = 0, h = 0 və işlənmir. Girişdə ən çox 30 test verilir.
Çıxış verilənləri
Hər testin nəticəsi ayrı bir sətirdə verilməlidir. Hər sətir "Case #: " ilə başlamalıdır, burada "#" testin nömrəsidir. Daha sonra həmin sətirdə n tam ədəd ardıcıllığı verilməlidir - h-dən böyük olmayan hündürlükdə BDS-yə daxil ediləcək zirvələrin ardıcıllığı. Sətirin sonunda artıq boşluqlar olmamalıdır. Əgər tələb olunan ağacı qurmaq mümkün deyilsə, "Impossible." (ikiqat dırnaq işarələri olmadan) çıxarılmalıdır.