المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۴:عملی مقدماتی دوم:سوال ۲

سوال ۲

یکی از دانش‌پژوهان ورزشکار المپیاد کامپیوتر، بعد از زدن سرویس پرشی در بازی والیبال مصدوم شده و خانم دکتر برای مداوای او به باشگاه آمده‌است. خانم دکتر بعد از مداوای او متوجه صف بلندی از دانش‌پژوهان المپیاد کامپیوتر روبروی در سایت می‌شود، یک صف بسیار بلند که برای اعلام نتیجه‌ی آزمون عملی دوم تشکیل شده‌است. به دلایل نامعلوم (احتمالن قوی بودن تست‌کیس‌ها) مدت زیادی است که بچه‌ها منتظرند و نتیجه‌ای اعلام نشده‌است. برای همین بچه‌ها خودشان سعی دارند رتبه‌ای حدودی برای خود تخمین بزنند.

روش آن‌ها به این صورت است که $k$ نفر اول صف بر اساس عملکردی که در آزمون داشته‌اند هر کدام تخمینی اولیه از رتبه‌ی خود می‌زنند و بقیه‌ی افراد صف با توجه به رتبه‌ی افراد جلوی خود، یک رتبه تخمینی برای خود در نظر می‌گیرند. آن‌ها به ترتیب (ابتدا فرد $k + 1$ام ، سپس $k + 2$ام و …)‌ به این صورت رتبه‌ی خود را تخمین می‌زنند که رتبه‌ی $k$ نفر جلوی خود را می‌پرسند (یعنی فرد $i$ام صف از افراد $i − k$ام تا $i − 1$ام صف رتبه‌‌ی تخمینی‌شان را می‌پرسد) و با توجه به این که خیلی خوش‌بین هستند، کوچکترین رتبه‌ای را که هیچ‌ یک از $k$ نفر جلویی برای خود در نظر نگرفته را به عنوان رتبه‌ی خود در نظر می‌گیرند.

تصویر زیر تخمین شش نفر اول را در صورتی که $k = 4$ باشد نشان می‌دهد.

ورودی

  • در سطر اول ورودی به ترتیب دوعدد طبیعی $k$ و $n$ آمده است.
  • سطر دوم دنباله‌ی $a_1, a_2, \cdots , a_k$ را نشان می‌دهد که در آن $a_i$ تخمین اولیه فرد $i$ام صف است.
  • ممکن است در بین $k$ نفر اول دو نفر رتبه‌ی یکسانی تخمین زده باشند.
  • $1 \leq k \leq 10^6$
  • $k < n \leq 10^{12}$
  • $1 \leq a_1, a_2, \cdots , a_k \leq 10^9$

خروجی

در تنها سطر خروجی تخمینی که فرد $n‌$ام صف از رتبه‌ی خود دارد را چاپ کنید.

زیرمسئله‌ها

  • زیرمسئله اول (۱۰ نمره): $k \leq 500$ و $n \leq 5000$
  • زیرمسئله دوم (۲۰ نمره): $k \leq 500$
  • زیرمسئله سوم (۴۰ نمره): $n, k \leq 10^5$
  • زیرمسئله چهارم (۲۰ نمره): $k \leq 10^5$
  • زیرمسئله پنجم (۱۰ نمره): بدون محدودیت اضافی

محدودیت‌ها

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

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

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

ابزار صفحه