Skip to content
TheChatArchiveThe Chat Archive
o1-mini-2024-09-12· OpenAIAi2 WildChat-4.8M (AI2)

محدودیت زمان: ۱ ثانیه محدودیت حافظه: ۲۵۶ مگابایت کاراکتر اصلی ۱ دوست دارد دانش آموزانش…

  1. 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++

  2. Assistant

    برای حل این مسئله، باید به ترتیب مراحل زیر عمل کنیم:

    1. خواندن ورودی:

      • مقدار n را که تعداد لامپ‌ها و کلیدهاست، می‌خوانیم.
      • سپس یک آرایه mapping را می‌خوانیم که نشان می‌دهد هر لامپ به کدام کلید متصل است.
      • در نهایت، وضعیت فعلی هر لامپ (0 یا 1) را می‌خوانیم.
    2. شناسایی کلیدهای مورد نیاز:

      • برای هر لامپ که روشن (1) است، کلید مرتبط با آن لامپ را انتخاب می‌کنیم.
    3. مرتب‌سازی کلیدها:

      • کلیدهای انتخاب شده را به ترتیب صعودی مرتب می‌کنیم تا خروجی نهایی به درستی نمایش داده شود.
    4. چاپ نتیجه:

      • کلیدهای مرتب شده را به عنوان خروجی چاپ می‌کنیم.

    در نظر داشته باشید که اگر تمام لامپ‌ها خاموش باشند، خروجی باید خالی باشد.

    در زیر کد کامل و توضیح داده شده به زبان 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';
    }
    

    توضیح کد:

    1. خواندن ورودی:

      • از std::vector برای ذخیره‌سازی نقشه‌ی کلیدها و وضعیت لامپ‌ها استفاده شده است.
      • با استفاده از ios::sync_with_stdio(false); و cin.tie(0); سرعت خواندن ورودی افزایش یافته است.
    2. جمع‌آوری کلیدها:

      • برای هر لامپی که روشن است، کلید مربوطه به لیست keys_to_press اضافه می‌شود.
    3. مرتب‌سازی و چاپ:

      • کلیدها با استفاده از تابع 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 خواهد بود که مطابق نمونه خروجی است.