یکی از دانشپژوهان ورزشکار المپیاد کامپیوتر، بعد از زدن سرویس پرشی در بازی والیبال مصدوم…
- User
یکی از دانشپژوهان ورزشکار المپیاد کامپیوتر، بعد از زدن سرویس پرشی در بازی والیبال مصدوم شده و خانم دکتر برای مداوای او به باشگاه آمدهاست. خانم دکتر بعد از مداوای او متوجه صف بلندی از دانشپژوهان المپیاد کامپیوتر روبروی در سایت میشود، یک صف بسیار بلند که برای اعلام نتیجهی آزمون عملی دوم تشکیل شدهاست. به دلایل نامعلوم (احتمالن قوی بودن تستکیسها) مدت زیادی است که بچهها منتظرند و نتیجهای اعلام نشدهاست. برای همین بچهها خودشان سعی دارند رتبهای حدودی برای خود تخمین بزنند.
روش آنها به این صورت است که k k نفر اول صف بر اساس عملکردی که در آزمون داشتهاند هر کدام تخمینی اولیه از رتبهی خود میزنند و بقیهی افراد صف با توجه به رتبهی افراد جلوی خود، یک رتبه تخمینی برای خود در نظر میگیرند. آنها به ترتیب (ابتدا فرد k + 1 k+1-ام ، سپس k + 2 k+2-ام و ...) به این صورت رتبهی خود را تخمین میزنند که رتبهی k k نفر جلوی خود را میپرسند (یعنی فرد i i-ام صف از افراد i − k i−k-ام تا i − 1 i−1-ام صف رتبهی تخمینیشان را میپرسد) و با توجه به این که خیلی خوشبین هستند، کوچکترین رتبهای را که هیچ یک از k k نفر جلویی برای خود در نظر نگرفته را به عنوان رتبهی خود در نظر میگیرند.
تصویر زیر تخمین شش نفر اول را در صورتی که k
4 k=4 باشد نشان میدهد.
توضیح تصویر
ورودی در سطر اول ورودی به ترتیب دوعدد طبیعی k k و n n آمده است.
سطر دوم دنبالهی a 1 , a 2 , . . . , a k a 1 ,a 2 ,...,a k را نشان میدهد که در آن a i a i تخمین اولیه فرد i i-ام صف است.
ممکن است در بین k k نفر اول دو نفر رتبهی یکسانی تخمین زده باشند.
1 ≤ k ≤ 1
000
000 1≤k≤1 000 000 k < n ≤ 1 0 12 k<n≤10 12
0 ≤ a 1 , a 2 , . . . , a k ≤ 1 0 9 0≤a 1 ,a 2 ,...,a k ≤10 9
خروجی در تنها سطر خروجی تخمینی که فرد n n-ام صف از رتبهی خود دارد را چاپ کنید.
زیرمسئلهها زیرمسئله نمره محدودیت ۱ ۱۰ k ≤ 500 k≤500 , n ≤ 5
000 n≤5 000 ۲ ۲۰ k ≤ 500 k≤500 ۳ ۴۰ k , n ≤ 100
000 k,n≤100 000 ۴ ۲۰ k ≤ 100
000 k≤100 000 ۵ ۱۰ بدون محدودیت اضافی مثال ورودی نمونه ۱ 4 5 4 7 2 2 Plain text خروجی نمونه ۱ 1 Plain text ورودی نمونه ۲ 4 6 4 7 2 2 Plain text خروجی نمونه ۲ 3 Plain text ورودی نمونه ۳ 7 12 1 2 3 4 3 2 1 Plain text خروجی نمونه ۳ 4 c++
- Assistant
برای حل این مسئله، باید روند تخمین رتبهی دانشپژوهان صف را به دقت شبیهسازی کنیم و از خصوصیات رفتار متوالی آن استفاده کنیم تا بتوانیم رتبهی نفر n-ام را بهسرعت محاسبه کنیم بدون اینکه نیاز به شبیهسازی تمامی افراد باشد. به دلیل بزرگ بودن مقدار n (تا (10^{12}))، نیاز به یک روش بهینه داریم.
مراحل حل مسئله:
-
مقدمهسازی:
- ابتدا k و n را میخوانیم.
- سپس تخمینهای اولیهی k نفر اول صف را میخوانیم.
-
محاسبهی Mex:
- Mex کوچکترین عدد طبیعی مثبت است که در مجموعهای از اعداد وجود ندارد. ما باید Mex پنجرهی جاری (آخرین k نفر) را بهدست آوریم.
-
شبیهسازی و شناسایی چرخه:
- پس از محاسبهی Mex برای مراحل اولیه، مشاهده میکنیم که پس از یک تعداد معین از مراحل، یک الگوی تکراری (چرخه) در تخمینها شکل میگیرد.
- این چرخه معمولاً طول (k + 1) دارد.
-
استفاده از چرخه برای محاسبهی رتبهی n-ام:
- اگر (n \leq k) باشد، تخمین اولیهی مربوط به آن فرد را چاپ میکنیم.
- اگر (n > k) باشد، از الگوی چرخهای استفاده میکنیم تا رتبهی n-ام را محاسبه کنیم.
-
پیادهسازی به زبان C++:
- برای بهینهسازی، از ساختارهای داده موثر مانند آرایهها استفاده میکنیم.
- از یک آرایهی شمارش برای نگهداری تعداد تکرار هر عدد در پنجرهی جاری استفاده میکنیم تا مقدار Mex به سرعت بهروزرسانی شود.
پیادهسازی نهایی:
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main(){ ios::sync_with_stdio(false); cin.tie(0); ll k, n; cin >> k >> n; vector<int> a(k); for(int &x: a) cin >> x; vector<int> window(k); vector<int> counts(k +2, 0); for(int i=0;i<k;i++) { window[i] = a[i]; if(a[i] <=k+1) counts[a[i]]++; } int mex =1; while(mex <=k+1 && counts[mex] >0){ mex++; } vector<int> cycle; int start=0; for(int i=0;i<k+1;i++){ int f = mex; cycle.push_back(f); if(f <=k+1){ counts[f]++; } int outgoing = window[start]; if(outgoing <=k+1){ counts[outgoing]--; } window[start] = f; if(outgoing < mex && outgoing >=1 && counts[outgoing] ==0){ mex = outgoing; } while(mex <=k+1 && counts[mex] >0){ mex++; } start = (start +1) %k; } if(n <=k){ cout << a[n-1]; } else{ ll m = n -k -1; ll cycle_length = k +1; ll cycle_idx = m % cycle_length; cout << cycle[cycle_idx]; } }توضیحات بیشتر:
- مدیریت پنجرهی جاری: از یک آرایه به اندازه k استفاده میکنیم که نقش پنجرهی جاری را دارد. هر بار که یک نفر جدید به پنجره اضافه میشود، نفر قدیمیتر از آن خارج میشود.
- بهروزرسانی Mex: پس از هر تغییر در پنجرهی جاری، مقدار Mex بهروز میشود تا همیشه کوچکترین عدد طبیعی مثبت که در پنجره نیست، مشخص شود.
- تشخیص چرخه: با شبیهسازی (k + 1) مرحلهی بعدی، الگوی چرخهای مشخص میشود که با استفاده از آن میتوان رتبهی n-ام فرد را محاسبه کرد.
پیچیدگی زمانی:
این الگوریتم با پیچیدگی زمانی (O(k)) اجرا میشود که برای مقادیر بزرگ k (تا (10^6)) قابل قبول است.
-