k-cı meandr
Bu tapşırıqda leksikoqrafik olaraq k-cı sırada olan n meandrını tapmalısınız.
Təsəvvür edin ki, müstəvidə bir düz xətt çəkilib. Sıra n olan meandr, bu düz xətti 2n dəfə kəsən qapalı bir müstəvi əyrisidir. Meandrı, çayın düz seqmentini körpülərlə kəsən qapalı dolama yol kimi düşünə bilərsiniz. Bu intuitiv tərif bir neçə rəsmi şərtlə dəqiqləşdirilməlidir: əyri öz-özünə kəsişməməli və ya toxunmamalıdır, əyrinin düz xətti kəsdiyi 2n nöqtə fərqli olmalıdır və bu nöqtələr həqiqətən kəsişmə nöqtələri olmalıdır, toxunma deyil. Əlavə olaraq, əyri və düz xətt yuxarıda göstərilənlərdən başqa ümumi nöqtələrə malik olmamalıdır.
Meandr çəkmək üçün əlverişli bir üsul müəyyən edək. Ümumi məhdudiyyət olmadan fərz edək ki, xətt üfüqi yerləşir və kəsişmə nöqtələri bir-birindən vahid məsafədə yerləşir. Qeyd edək ki, əyrinin kəsişmə nöqtələri onu 2n hissəyə bölür. Bu hissələrdən bəziləri xəttin üstündə, digərləri isə altında yerləşir. Bu hissələrin hər birini xəttin müvafiq seqmentində diametr kimi qurulmuş yarımdairə şəklində təsvir edək və lazım olduqda xəttin üstündə və ya altında yerləşdirək. Sübut etmək olar ki, bu şəkildə əldə edilən şəkil meandrdır: xüsusən, bu şəkildə qurulmuş əyri öz-özünə kəsişmələrə və ya toxunmalara malik deyil. Əksinə də doğrudur: hər bir meandr verilmiş şəkilə davamlı (homeomorfik) çevrilmələrlə çevrilə bilər.
İndi meandru bir sıra şəklində yazmağı öyrənək. Verilən prosedura uyğun olaraq təsvir edilmiş meandrı nəzərdən keçirək. Xətt boyunca soldan sağa gedək və hər dəfə kəsişmə nöqtəsi ilə qarşılaşdığımızda qeyd edək. Hər belə nöqtə üçün əyrinin iki hissəsi ona qoşulur: biri xəttin üstündə, digəri isə altında. Bu hissələrin hər biri cari kəsişmə nöqtəsindən sola və ya sağa gedən yarımdairədir. Dörd mümkün halı fərqləndirək və hər birini ingilis əlifbasının hərfi ilə qeyd edək:
Hər iki yarımdairə sağa gedirsə, bu kəsişmədə əyrinin açıldığını deyəcəyik, bu faktı O (Open) hərfi ilə qeyd edək.
Hər iki yarımdairə sola gedirsə, bu kəsişmədə əyrinin bağlandığını deyəcəyik, bu faktı C (Close) hərfi ilə qeyd edək.
Aşağıdakı yarımdairə sola, yuxarıdakı isə sağa gedirsə, bu kəsişmədə əyrinin yuxarıya doğru getdiyini deyəcəyik, bu faktı U (Up) hərfi ilə qeyd edək.
Yuxarıdakı yarımdairə sola, aşağıdakı isə sağa gedirsə, bu kəsişmədə əyrinin aşağıya doğru getdiyini deyəcəyik, bu faktı D (Down) hərfi ilə qeyd edək.
Soldan sağa hərəkət edərək, kəsişmələri göstərmək üçün 2n hərf yazacağıq. Məlum olur ki, bu məlumat meandru birmənalı olaraq bərpa etmək üçün kifayətdir. Bu prosesi çayın axını boyunca (soldan sağa) hərəkət etmək və körpülərin yaxınlığında yolların konfiqurasiyasını qeyd etmək kimi təsəvvür etmək olar.
İki meandr, onların notları fərqli olduqda fərqli hesab olunur. Məsələn, sıra 3 olan səkkiz fərqli meandr aşağıda göstərilmişdir.
Verilmiş sıra n üçün bütün fərqli meandrləri götürək, onları notlara görə leksikoqrafik olaraq sıralayaq. Verilmiş sıra n və k nömrəsinə görə leksikoqrafik olaraq k-cı sırada olan n meandrının notunu çıxarın.
Giriş verilənləri
İki tam ədəd n və k (1 ≤ n ≤ 25, 1 ≤ k ≤ 10^11): meandrın sırası və nömrəsi. Göstərilən parametrlərlə meandrın mövcudluğu təmin edilir.
Çıxış verilənləri
2n hərfdən ibarət bir sıra çıxarın: sıra n olan meandrın leksikoqrafik olaraq k-cı notu.