پاسخ سوال دزد پرنده کوئرا

پاسخ سوال دزد پرنده کوئرا

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

پاسخ سوال دزد پرنده کوئرا

دزد با مهارت، در دزدی به مهارت بالا رفتن و جانگولربازی (‌jungular play) نیاز دارد؛ چرا که بعد از پیدا کردن دوربین‌های فروشگاه و ورود به آن، او دریافت که تیله‌ها در طبقه‌ی آخر است. او در طبقه‌ی اول فروشگاه بوده و باید به طبقه‌ی آخر یعنی طبقه‌ی $n$ ام برود. هر طبقه دو پنجره دارد. یکی در سمت راست طبقه و یکی در سمت چپ طبقه(هر طبقه را یک پاره خط افقی فرض کنید که پنجره‌ها در دو لبه‌ی آن قرار دارد). اگر دزد در طبقه‌ی $k$ است، تنها می‌تواند به طبقه‌ی $k+1$ برود. اگر برای مثال او در طبقه‌ی k شود، دو روش برای رفتن به طبقه‌ی بعدی وجود دارد:

• از پنجره‌ی سمت راست طبقه‌ی k ام خارج شده و از طریق پنجره‌ی سمت راست، به طبقه‌ی k+1 وارد شود.
• از پنجره‌ی سمت چپ طبقه‌ی k ام خارج شده و از طریق پنجره‌ی سمت چپ، به طبقه‌ی k+1 وارد شود.

متاسفانه در بعضی از طبقات، پلیس وجود دارد. در هر طبقه حداکثر یک پلیس وجود دارد. در طبقه‌ی اول و آخر پلیس وجود ندارد. هر پلیس چون خسته است(ساعت کاری شون زیاده!)، تنها می‌تواند مراقب یکی از پنجره‌های طبقه‌ای که در آن است، شود؛ یعنی دزد نمی‌تواند از آن پنجره وارد آن طبقه شود و در عین حال نمی‌تواند در آن طبقه از پنجره‌ای که پلیس مراقب آن است، خارج شود و به طبقه‌ی بالا برود. یعنی اگر مثلا پلیسی در طبقه‌ی k ام هست و مراقب پنجره‌ی راست شود و دزد بخواهد از طبقه‌ی k-1 ام به طبقه‌ی k+1 ام برود، باید از پنجره‌ی چپ طبقه‌ی k-1 ام خارج شده و از طریق پنجره‌ی چپ، به طبقه‌ی k ام وارد شود. سپس باید دوباره از پنجره‌ی سمت چپ طبقه‌ی $k$ ام استفاده کرده و از طریق پنجره‌ی چپ، به طبقه‌ی k+1 ام وارد شود. دقت کنید که اگر در طبقه‌ای هیچ پلیسی قرار نگیرد، از هر دو پنجره‌ی آن می‌توان خارج و از هر دو پنجره‌ی آن می‌توان به آن وارد شد. دزد مکان پلیس‌ها و پنجره‌ای را که هر کدام مراقبش هستند، می‌داند. او به شما این اطلاعات را می‌دهد و شما می‌خواهد که به او بگویید که آیا می‌تواند به طبقه‌ی آخر برود یا خیر.

ورودی سوال دزد پرنده

در هر ورودی، تعدادی تست آمده‌است که برنامه‌ی شما باید به آن‌ها به ترتیب پاسخ دهد. در سطر اول هر ورودی یک عدد t آمده است که نمایانگر تعداد تست‌هایی است که باید در این ورودی جواب داده شوند. سپس در هر تست:

در سطر اول هر تست دو عدد n و $k$ آمده‌ است که نمایانگر تعداد طبقات و تعداد پلیس‌‌ها در این تست است. در $k$ سطر بعدی، در سطر i، ابتدا a_i​ که نمایانگر طبقه‌ی حضور پلیس $i$ ام است،آمده است. سپس یک عدد آمده است که نمایانگر پنجره ایست که پلیس $i$ ام مراقب آن است که این عدد یا 0 است و یا 1:

0: به معنای اینکه پلیس i ام مراقب پنجره‌ی راست است.

1: به معنای اینکه پلیس i ام مراقب پنجره‌ی چپ است.

$$3\le n\le 100000$$0

$$0\le k\le n-2$$2

2 ≤ ai​ ≤ n−1

مجموع $n$ در تست‌های هر ورودی از$200000$ بیش‌تر نیست.

خروجی سوال دزد پرنده

در تنها سطر خروجی هر تست یکی از دو کلمه‌ی زیر را خروجی دهید:

• No: به معنای دزد نمی‌تواند به طبقه‌ی آخر برسد
• Yes: به معنای اینکه دزد می‌تواند به طبقه‌ی آخر برسد

حل سوال دزد پرنده

#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;
 
int main()
{
    int t;
    cin >> t;
    string pasokh[t];
    for(int i=0; i<t; i++)
    {
        int n, k;
        cin >> n >> k;
        
        int polis[k][2];
        for(int j=0; j<k; j++)
        {
            cin >> polis[j][0];
            cin >> polis[j][1];
        }
        
        if(k <= 1 || n == 3)
        {
            pasokh[i] = "Yes";
            continue;
        }
        
        qsort(polis, k, sizeof(*polis),
        [](const void *arg1, const void *arg2)->int
        {
            int const *lhs = static_cast<int const*>(arg1);
            int const *rhs = static_cast<int const*>(arg2);
            return (lhs[0] < rhs[0]) ? -1
                :  ((rhs[0] < lhs[0]) ? 1
                :  (lhs[1] < rhs[1] ? -1
                :  ((rhs[1] < lhs[1] ? 1 : 0))));
        });
        
        for(int j=1; j<k; j++)
        {
            if(abs(polis[j-1][0] - polis[j][0]) <= 1)
            {
                if(polis[j-1][1] != polis[j][1])
                {
                    pasokh[i] = "No";
                    break;
                }
            }
            
            if(j == k-1)
                pasokh[i] = "Yes";
        }
    }
    for(int i=0; i<t; i++)
    {
        cout << pasokh[i] << endl;
    }
    
    return 0;
}

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

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

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