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

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

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

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

 

در مورد سایت کوئرا بیشتر بخوانید…

 

تمرین دزد پرنده کوئرا + سی پلاس پلاس

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

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

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

 

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

در هر ورودی، تعدادی تست آمده‌است که برنامه‌ی شما باید به آن‌ها به ترتیب پاسخ دهد.

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

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

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

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

0

n-22

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

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

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

  • 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;
}

 

 

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

 

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

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

موفق باشید.

برای امتیاز به این نوشته کلیک کنید!
[کل: 0 میانگین: 0]