محدودیت زمان: ۱ ثانیه محدودیت حافظه: ۲۵۶ مگابایت کاراکتر اصلی ۱ دوست دارد دانش آموزانش…
- User
محدودیت زمان: ۱ ثانیه محدودیت حافظه: ۲۵۶ مگابایت
کاراکتر اصلی ۱ دوست دارد دانش آموزانش (که آنها را با نام کاراکترهای کمکی میشناسیم) را به درس هندسه علاقهمند کند به همین خاطر از وسیلهای کمک آموزشی استفاده میکند که یک صفحه با n n لامپ است که لامپها با شمارههای ۱ تا n n شمارهگذاری شدهاند و همچنین در زیر صفحه هم n n کلید با شمارههای ۱ تا n n برای روشن کردن لامپها وجود دارد.
هریک از لامپها به یک کلید در زیر صفحه وصل هستند. به علت مشغلهی زیاد، کاراکتر اصلی ۱ فرصت نکرده است هر لامپ را به کلید همشمارهاش وصل بکند و بصورت تصادفی هر لامپ را به یک کلید وصل کرده است، بطوری که هیچ کلیدی از n n کلید زیر صفحه نیست که لامپی به آن متصل نباشد.
پس از زنگ تفریح وقتی کاراکتر اصلی ۱ به کلاس بر میگردد میبیند بعضی لامپها روشن و بعضی دیگر خاموشاند، اما به دلیل این که هر کلید به لامپی که ممکن است همشمارهاش نباشد متصل است، کار برای کاراکتر اصلی ۱ سخت است، چون او میخواهد قبل از جمع کردن وسیله آموزشی لامپهایش را خاموش کند تا باتری آن بیهوده هدر نرود.
باتوجه به وضعیت فعلی لامپها و اینکه هر کلید کدام لامپ را روشن میکند، در خروجی شمارهی کلیدهایی که باید بزنیم تا همهی لامپها خاموش شوند را چاپ کنید.
ورودی در خط اول ورودی عدد طبیعی n n داده میشود.
در خط دوم ورودی n n عدد طبیعی میآیند که i iامین آنها شمارهی کلیدی است که به لامپ i iام متصل است.
و در خط آخر ورودی n n عدد از مجموعهی 0 , 1 0,1 میآیند که i iامین عدد نشاندهندهی خاموش یا روشن بودن لامپ i iام است. اگر عدد i iام ۰ باشد یعنی لامپ i iام خاموش و در صورتی که عدد i iام ۱ باشد، لامپ i iام روشن است.
1 ≤ n ≤ 100
000 1≤n≤100 000
خروجی در یک خط شماره کلیدهایی را چاپ کنید که اگر آنها را یکبار بفشاریم وضعیت همهی لامپها در انتها خاموش باشد. دقت کنید ترتیب خروجی دادن شماره کلیدها باید صعودی باشد. (یعنی اگر کلیدهایی که فشردن آنها حالت مطلوب را میسازد پیدا کنید اما بصورت صعودی چاپشان نکنید نمرهی سوال را نمیگیرید)
مثال ورودی نمونه 10 3 6 1 2 10 4 5 9 8 7 0 0 0 1 1 1 1 1 1 1 Plain text خروجی نمونه 2 4 5 7 8 9 10 Plain text توضیح در مثال دادهشده لامپهای ۴ تا ۱۰ روشناند و باید آنها را خاموش کنیم، پس نیاز است کلیدهای 2 10 4 5 9 8 7 را فشار دهیم. اما در صورت سوال گفته شده که بایستی کلیدها باترتیب صعودی چاپ شوند، پس بجای 2 10 4 5 9 8 7 در خروجی 2 4 5 7 8 9 10 را چاپ میکنیم. c++
- Assistant
برای حل این مسئله، باید به ترتیب مراحل زیر عمل کنیم:
-
خواندن ورودی:
- مقدار
nرا که تعداد لامپها و کلیدهاست، میخوانیم. - سپس یک آرایه
mappingرا میخوانیم که نشان میدهد هر لامپ به کدام کلید متصل است. - در نهایت، وضعیت فعلی هر لامپ (
0یا1) را میخوانیم.
- مقدار
-
شناسایی کلیدهای مورد نیاز:
- برای هر لامپ که روشن (
1) است، کلید مرتبط با آن لامپ را انتخاب میکنیم.
- برای هر لامپ که روشن (
-
مرتبسازی کلیدها:
- کلیدهای انتخاب شده را به ترتیب صعودی مرتب میکنیم تا خروجی نهایی به درستی نمایش داده شود.
-
چاپ نتیجه:
- کلیدهای مرتب شده را به عنوان خروجی چاپ میکنیم.
در نظر داشته باشید که اگر تمام لامپها خاموش باشند، خروجی باید خالی باشد.
در زیر کد کامل و توضیح داده شده به زبان C++ ارائه شده است:
#include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; // mapping[i] will hold the key connected to lamp i+1 vector<int> mapping(n); for(int &x : mapping) cin >> x; // status[i] will hold the status of lamp i+1 vector<int> status(n); for(int &x : status) cin >> x; vector<int> keys_to_press; for(int i=0;i<n;i++){ if(status[i]==1){ keys_to_press.push_back(mapping[i]); } } sort(keys_to_press.begin(), keys_to_press.end()); if(!keys_to_press.empty()){ for(int i=0;i<keys_to_press.size();i++){ if(i>0) cout << ' '; cout << keys_to_press[i]; } } cout << '\n'; }توضیح کد:
-
خواندن ورودی:
- از
std::vectorبرای ذخیرهسازی نقشهی کلیدها و وضعیت لامپها استفاده شده است. - با استفاده از
ios::sync_with_stdio(false);وcin.tie(0);سرعت خواندن ورودی افزایش یافته است.
- از
-
جمعآوری کلیدها:
- برای هر لامپی که روشن است، کلید مربوطه به لیست
keys_to_pressاضافه میشود.
- برای هر لامپی که روشن است، کلید مربوطه به لیست
-
مرتبسازی و چاپ:
- کلیدها با استفاده از تابع
sortبه ترتیب صعودی مرتب میشوند. - سپس به صورت جداگانه با فاصله چاپ میشوند. اگر هیچ کلیدی برای فشار دادن وجود نداشته باشد، فقط یک خط جدید چاپ میشود.
- کلیدها با استفاده از تابع
توضیح نمونه ورودی:
برای نمونه ورودی داده شده:
10 3 6 1 2 10 4 5 9 8 7 0 0 0 1 1 1 1 1 1 1لامپهای ۴ تا ۱۰ روشن هستند و کلیدهای متصل به آنها به ترتیب
2, 10, 4, 5, 9, 8, 7هستند. پس پس از مرتبسازی، خروجی به شکل2 4 5 7 8 9 10خواهد بود که مطابق نمونه خروجی است. -