Uzb Eng

0027. Poyezdlar
: 2 c
: 64

Kichik Erkin poyezdni yaxshi koradi. Uning tugilgan kuniga temir yol oyinchogini sovga qilishdi. Bu komplektga 1 dan n gacha raqamlangan n ta vagondan tashkil topgan poyezd ham kiradi.
Erkinning sevimli mashguloti maxsus tupik saralash orqali poyezdni saralash bolib qoldi.
Tupikka ong tarafdan n ta vagondan iborat poyezd keladi. Keyin vagonlar saralash tupigiga bitta-bitta bolib kirib keladi va chap tarafdan chiqib ketadi. Tupik judayam uzun bolib, unda bir vaqtning ozida ixtiyoriy sondagi vagonlar sigishi mumkin.
Erkinga saralash tupigi orqali poyezdni saralash yoqadi. Bunda tupikning chap tarafida vagonlar 1 ta to n gacha bolib saralanich chiqishi lozim.
Masalan, poyezdda 4 ta vagon bor va ular 3, 1, 2, 4 tartibda. Ularni quyidagicha saralash mumkin. 3-vagonni tupikka kiritamiz. Songra 1-vagonni ham tupikka kiritamiz. 1-vagonni tupikdan chiqarib olamiz. 2-vagonni tupikka kiritamiz va 2 vagonni tupikdan chiqarib olamiz. 3-vagonni tupikdan chiqarib olamiz. Eng oxiri 4 vagonni tupikka kiritamiz va tupikdan chiqarib olamiz.
Albatta, hamma poyezdlarni bunday saralab bolmaydi. Masalan, 3 vagonli va vagonlari 2, 3, 1 bolib raqamlangan poyezdni saralab bolmaydi.
Erkin varaqqa uzunligi n bolgan barcha poyezdlarni leksikografik tartibini yozib chiqdi. Ularni tupik orqali saralash mumkin. Agarda shunday i (1 < i < n) mavjud bolsa, yani barcha j < i uchun aj= bj, ai < bi bajarilsa, leksikografik tartibda (a1, a2, . . ,.an) poyezd (b1, b2, . . ,.bn) poyezddan oldin turadi.
Masalan, vagonlari uchta bolgan barcha poyezdlarni tupik orqali saralash mumkin. Ular leksikografik tartibda quyidagi korinishda yoziladi: (1,2,3), (1,3,2), (2,1,3), (3,1,2), (3,2,1)
Erkin varagini yoqotib qoydi va uni quyidagi savol qiziqtiradi: uning varagida k -raqam bilan qaysi poyezd yozilgan. Unga buni aniqlashda yordam bering.

:
Ikkita n va k sonlari berilgan (1 < n < 30, 1 < k < 1018).

:
N ta burun sonni chiqaring: tupik yordamida saralangan n vagonli poyezdni leksikografik tartib boyicha k chisi.
Agarda tupik yordamida n ta vagonli poyezdni k dan kichik songacha saralash mumkin bolsa, yani saralashlar soni k dab kichik bolsa 1 chiqaring.

4 1
4 3
4 15
12 3 4
13 2 4
-1
:
: XII 2011


Design by TUIT © 2012-2017 TUIT Online Judge. All rights reserved.