پاسخ سوال درِ آزمایشگاه کوئرا

پاسخ سوال درِ آزمایشگاه کوئرا

در این نوشته تمرین “دایره عجیب” که در وب‌سایت کوئرا موجود است را برای شما کاربران عزیز حل کرده‌ایم.

پاسخ سوال درِ آزمایشگاه کوئرا

فامیل دور که در کار در فعالیت دارد، به تازگی مسئول در آزمایشگاه شده است. او می‌خواهد از کار‌های داخل آزمایشگاه سر در بیاورد. فامیل دور که خیلی به کارش حساس است، هرچیزی که از در رد می‌شود را یادداشت می‌کند. به همین دلیل او یک لیست از تمامی مواد داخل آزمایشگاه دارد. هم‌چنین او با مشاهدات طولانی تمامی واکنش‌ها را هم به خاطر سپرده است. هر واکنش به شکل a_1 + a_2 + a_3 … + a_p a1​+a2​+a3​...+ap​→b1​+b2​+b3​+...+bq​ است. یعنی اگر در واکنشی همه‌ی a_1​ تا a_p​ وجود داشت، همه‌ی b_1​ تا b_q​ به وجود می‌آیند. همه‌ی $a$ها متفاوت و همه‌ی $b$ها متفاوت اند ولی ممکن است $i$ و jی هست که ai​=bj​(مانند کاتالیزگرها). حالا فامیل می‌خواهد بداند با این واکنش‌ها چه موادی را می‌تواند دارا شود. دقت کنید هر ماده‌ای را می‌توان به هر اندازه‌ای رقیق کرد(یعنی اگر از یک نوع ماده در یک زمان داشته، می‌توانیم برای همیشه از آن استفاده کنیم).

ورودی سوال درِ آزمایشگاه

در سطر اول ورودی سه عدد طبیعی $n$ و m و $k$ آمده‌است که به ترتیب نشان‌دهنده‌ی تعداد مواد شناخته شده، تعداد مواد موجود در آزمایشگاه و تعداد واکنش‌ها است. در سطر بعد $m$ عدد آمده است که نشان‌دهنده‌ی مواد موجود در آزمایشگاه هستند. تضمین میشود این اعداد طبیعی، متفاوت و نابیش‌تر از n هستند. سپس $k$ واکنش می‌آید. هر واکنش دارای سه سطر ورودی است. سطر اول حاوی دو عدد طبیعی مانند p و q است. در سطر دوم $p$ عدد متفاوت آمده‌است که نشان‌دهنده‌ی واکنش‌دهنده‌ها هستند. و در سطر سوم $q$ عدد متفاوت آمده که نمایان‌گر فراورده‌های واکنش هستند.

$$1\le n,m,k\le 300000$$

مجموع همه‌ی p و $q$ها حداکثر سیصدهزار است.

خروجی سوال درِ آزمایشگاه

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

حل سوال درِ آزمایشگاه

#include <iostream>
#include <math.h>
#include <algorithm>
#include <vector>
using namespace std;
 
int main()
{
    int n, m, k;
    cin >> n >> m >> k;
    bool mojod[n] = {false};
    vector<int> can;
    int temp;
    for(int i=0; i<m; i++)
    {
        cin >> temp;
        mojod[temp-1] = true;
        can.push_back(temp);
    }
    
    vector<int> vakonesh[k][2];
    for(int i=0; i<k; i++)
    {
        int p,q;
        cin >> p >> q;
        
        for(int j=0; j<p; j++)
        {
            cin >> temp;
            vakonesh[i][0].push_back(temp);
        }
        
        for(int j=0; j<q; j++)
        {
            cin >> temp;
            vakonesh[i][1].push_back(temp);
        }
    }
    bool oks[k] = {false};
    int vsize;
    bool changed = false;
    for(int i=0; i<k; i++)
    {
        
        if(oks[i] && i<k-1)
            continue;
        else if(oks[i])
        {
            if(changed)
            {
                i = -1;
                changed = false;
            }
            continue;
        }
        
        vsize = vakonesh[i][0].size();
        bool mishe = true;
        for(int j=0; j<vsize; j++)
        {
            if(mojod[vakonesh[i][0][j]-1] == false)
            {
                mishe = false;
                break;
            }
        }
        
        if(mishe)
        {
            vsize = vakonesh[i][1].size();
            for(int j=0; j<vsize; j++)
            {
                mojod[vakonesh[i][1][j]-1] = true;
            }
            changed = true;
            oks[i] = true;
        }
        
        if(i == k-1)
        {
            if(changed)
            {
                i = -1;
                changed = false;
            }
            continue;
        }
    }
    
    int tedad = 0;
    for(int i=0; i<n; i++)
    {
        if(mojod[i])
        {
            tedad++;
        }
    }
    cout << tedad << endl;
    for(int i=0; i<n; i++)
    {
        if(mojod[i])
        {
            cout << i+1 << " ";
        }
    }
    return 0;
}

منبع سوال‌: وب‌سایت کوئرا

اگر روش حل بهتری برای “تمرین درِ آزمایشگاه” دارید برای ما ارسال کنید تا با نام خودتان به اشتراک بگذاریم.

اگر سوال خاصی را مدنظر دارید در بخش نظرات برای ما ارسال کنید تا حل آن سوال را در الویت محتوای سایت بگذاریم.