المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی انتخاب تیم:دوره‌ی ۲۳:سوال ۵

Notebook

علی کوچولو یک جایگشت به طول ‎$n$‎ و یک دفتر ‎$\dbinom{n+1}{2}$‎ صفحه‌ای دارد، ولی حوصله‌اش سر رفته. برای همین از برادر بزرگش حامد می‌خواهد برایش فیلم بگذارد. ولی از آنجایی که فیلم‌های حامد به سن علی نمی‌خورد و برایش بدآموزی دارد، حامد او را به دنبال نخود سیاه می‌فرستد و به او می‌گوید اگر می‌خواهد فیلم ببیند، تمام زیر‌رشته‌های جایگشتش (‎یک زیر رشته از جایگشت یک زیردنباله از جایگشت می‌باشد که اعضای آن بصورت متوالی در جایگشت ظاهر شده باشند‎) را به ترتیب مجموعه‌ای در دفترش بنویسد (هر صفحه یک زیردنباله)‌ و زیردنباله نوشته شده در صفحه ‎$k$‎ام را برایش بیاورد. علی کوچولو با این که بچه است ولی می‌داند تا دفتر پرشود، خودش ‎۱۸‎ سالش می‌شود‎!‎ ولی برای ضایع کردن برادرش از شما می‌خواهد زیردنباله ‎$k$‎ام را زود برایش پیدا کنید. به او کمک کنید.

یک زیردنباله از یک زیردنباله دیگر از نظر مجموعه‌ای کوچک‌تر است، اگر مجموعه اعضای آن از نظر الفبایی کوچک‌‌تر از مجموعه دوم باشد.

یک مجموعه از نظر الفبایی از یک مجموعه دیگر کوچک‌‌تر است، اگر یک ‎$i$‎ در مجموعه اول وجود داشته ‌باشد که مجموعه اعضای کوچک‌تر از ‎$i$‎ در هر دو مجموعه برابر باشند و مجموعه دوم شامل ‎$i$‎ نباشد‎.

ورودی

  • در سطر اول ورودی به ترتیب دو عدد صحیح ‎$n$‎ و ‎$k$‎ آمده است.
  • در سطر بعد ‎$n$‎ عدد آمده‌اند که یک جایگشت از اعداد ‎$1$‎ تا ‎$n$‎‌ را مشخص می‌کنند.
  • ‎ $1 \leq n \leq 10^5$‎.
  • ‎ $1 \leq k \leq \dbinom{n+1}{2}$‎.
  • دقت کنید که ممکن است عدد ‎$k$‎ در عدد صحیح ‎۳۲‎ بیتی گنجیده نشود.

خروجی

در یک سطر اعداد زیردنباله ‎$k$‎ام را چاپ کنید‎.

زیرمسئله‌ها

  • زیرمسئله‌ی اول (۱۰ نمره): در همه‌ی تست‌ها ‎$n\leq 200$‎.
  • زیرمسئله‌ی دوم (۳۰ نمره): در همه‌ی تست‌ها ‎$n\leq 1000$‎.
  • زیرمسئله‌ی سوم (۶۰ نمره): در همه‌ی تست‌ها ‎$n\leq 10^5$‎.

محدودیت‌ها

  • محدودیت زمان: ۲ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

ورودی و خروجی نمونه

ورودی نمونه خروجی نمونه
5 7
‎3 1 5 2 4
1 5
5 3
‎3 1 5 2 4
1 5 2 4

توضیحات

محتویات دفتر در دو تست اول:

‎3 1 5 2 4
‎3 1 5 2 ‎
‎1 5 2 4 ‎
‎1 5 2 ‎
‎3 1 5 ‎
‎3 1 ‎
‎1 5 ‎
‎1 ‎
5 2 4
‎2 4 ‎
‎5 2 ‎
‎2 ‎
‎3 ‎
‎4 ‎
‎5 ‎


ابزار صفحه