پاسخ سوال تیله‌های توی کیسه کوئرا

پاسخ سوال تیله‌های توی کیسه کوئرا

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

پاسخ سوال تیله‌های توی کیسه کوئرا

دزد با مهارت، به طبقه‌ی آخر رسید. او در آنجا با یک گاوصندوق مواجه شد که شنیده بود که پر از تیله است. اما او در اینجا با یک سد دفاعی محکم مواجه شد. پروفسورباقر که مسئول طراحی سیستم دفاعی فروشگاه بود (و خیلی هم ناشی بود)، موقع طراحی طبقه‌ی آخر، برای اینکه دزدی نتواند به گاوصندوق راه پیدا کند، بر روی زمین تیله ریخته بود تا هر کس بخواهد به گاوصندوق برسد، روی این تیله‌ها لیز بخورد و سپس به زمین نیز (چی؟) بخورد. وقتی دزد به طبقه‌ی آخر رسید، متوجه شد که بر روی زمین مقدار زیادی تیله ریخته شده است و او هم که به دزدی تیله آمده بود؛ پس شروع کرد به جمع کردن تیله‌های روی زمین. او تیله ها را در ‌$n$ کیسه ریخت. بعد از آن از ساختمان خارج شد و به پیش عمو (که بسیار پول پرست است) رفت تا کیسه‌هایش را بفروشد اما عمو در حال پرستش بود و در آن لحظه نمی‌توانست به دیدار دزد بیاید. برای همین دزد به اتاق انتظار رفت تا منتظر عمو بماند. دزد کیسه‌ها را بر روی یک میز در یک ردیف چید و منتظر ماند تا عمو بیاید. او کیسه‌ها را از یک تا n به ترتیب از چپ به راست نام گذاری کرد و می‌داند که در کیسه‌ی $i$، a_i​ تیله وجود دارد. در همین حین ناگهان نکته‌ای به ذهن دزد رسید: عمو همیشه موقع خرید تیله، یک بازه‌ی $d$ تایی پشت سر هم از کیسه‌ها را انتخاب می‌کند و اگر تعداد تیله ها در این $d$ کیسه زوج بود، پولش را می‌دهد و گرنه با لگد دزد را از دفترکارش بیرون می‌اندازد (بالاخره عمو که نمی‌تواند خدایش را به راحتی به دست دزد بدهد که خدایش است ها علف خرس که نیست). به همین دلیل دزد مجبور است که تعداد تیله‌ها در برخی کیسه‌ها را تغییر دهد تا اگر عمو هر بازه‌ی $d$ تایی پشت سر هم از کیسه‌ها را انتخاب کرد، تعداد تیله‌ها در مجموع این کیسه‌ها زوج شود. خوشبختانه دزد تعدادی تیله در جیبش دارد. او در یک عملیات می‌تواند یک کیسه را انتخاب کند و دقیقا یک تیله به آن اضافه کند. به او بگویید که کمینه‌ی تعداد عملیات برای این که کیسه‌ها را مطابق میل عمو کند چقدر است.

ورودی سوال تیله‌های توی کیسه

در خط اول ورودی به ترتیب n و $d$ آمده است که $n$ نمایانگر تعداد کیسه‌ها و $d$ نمایانگر اندازه‌ی بازه‌‌ی پشت سر همی از کیسه‌ها است که عمو انتخاب می‌کند و تعداد تیله‌ها در مجموع این $d$ کیسه باید زوج شود. سپس در خط بعد $n$ عدد آمده است که عدد i ام نمایانگر تعداد تیله‌ها در کیسه‌ی i است.

$$1\le d\le n\le 1000000$$0

0 ≤ ai​ ≤ 1000000000

خروجی سوال تیله‌های توی کیسه

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

حل سوال تیله‌های توی کیسه

#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;
 
int main()
{
    int n, d;
    cin >> n >> d;
    int tile[n];
    for(int i=0; i<n; i++)
        cin >> tile[i];
    
    int num=0;
    int index = -1;
    int maxsMinimum = 1000000000;
    int m = -1;
    for(int i=0; i<d; i++)
    {
        int index = i;
        int z=0, f=0;
        while(index < n)
        {
            if(tile[index] % 2 == 0)
                z++;
            else
                f++;
            index += d;
        }
        
        num += min(z , f);
        if(max(z, f) < maxsMinimum)
        {
            maxsMinimum = max(z, f);
            m = min(z, f);
            index = i;
        }
        
        if(min(z, f) == z)
        {
            int ind = i;
            while(ind < n)
            {
                if(tile[ind] % 2 == 0)
                    tile[ind] ++;
                ind += d;
            }
        }
        else
        {
            int ind = i;
            while(ind < n)
            {
                if(tile[ind] % 2 == 1)
                    tile[ind] ++;
                ind += d;
            }
        }
    }
    
    bool zojiat = true;
    for(int i=0; i<d; i++)
    {
        if(tile[i] % 2 == 1)
            zojiat = !zojiat;
    }
    
    if(zojiat)
        cout << num;
    else
    {
        num -= m;
        num += maxsMinimum;
        cout << num;
    }
    
    return 0;
}

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

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