پاسخ سوال وزیر و تقسیم زمین کوئرا

پاسخ سوال وزیر و تقسیم زمین کوئرا

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

پاسخ سوال وزیر و تقسیم زمین کوئرا

وزیر شهر شکرستان می‌خواهد از n نفر از اشراف، زمین کشاورزی بخرد و آن را به مردم بفروشد. همه‌ی زمین‌ها به شکل یک مربع $1\times 1$ و کنار هم، در یک ردیف قرار دارند. هر یک از این اشراف برای زمین خودش یک قیمت به وزیر اعلام کرده است. اکنون وزیر می‌خواهد این n زمین را از اشراف خریداری کند و به روش زیر تقسیم کرده و به مردم بدهد.

1. زمین‌ها را به تعدادی بازه پشت سر هم افراز کند به طوری که مساحت زمین‌های همه بازه با هم برابر شوند.
2. مجموع قیمت‌ زمین‌های همه بازه‌ها با هم برابر شوند.
3. تعداد بازه‌ها بیشینه شود.

شما با اعلام کردن تعداد قسمت‌ها با شرایط فوق، به وزیر کمک کنید تا زمین‌ها را به مردم بدهد.

ورودی سوال وزیر و تقسیم زمین

در خط اول ورودی یک عدد صحیح $n$ که برابر تعداد زمین‌ها است داده می‌شود. در خط بعدی n عدد صحیح داده می‌شود که عدد iام برابر ai​ است که همان قیمتی است که اشراف برای زمین $i$ام اعلام کردند.

$$1\le n\le 1000000$$

1 ≤ ai​ ≤ 1000000000

خروجی سوال وزیر و تقسیم زمین

در یک خط خروجی بیشینه تعداد بازه‌ها را چاپ کنید.

حل سوال وزیر و تقسیم زمین

#include<bits/stdc++.h>

#define watch(x) cout<<(#x)<<" is "<<(x)<<"\n"
#define print(x) cout<<x<<"\n"
#define For(i,x,y) for(i = x; i < y; i++)
typedef std::vector<int> vi;
typedef std::vector<std::vector<int>> vvi;
typedef long long ll;
int INF = 999999;
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    int q,x;
    cin>>q;
    vi vec;
    for(int i = 0; i < q; i++){
        cin>>x;
        vec.push_back (x);
    }
    for(int i = q; i > 0;i--){
        if(q % i == 0){
            int sum = 0;
            for(int j = 0; j < q / i; j++){
                sum += vec[j];
            }
            int j = 0;
            for(; j < i; j++){
                int temp = 0;
                for(int k = (j) * (q / i); k < (j + 1) * (q / i); k++){
                    temp += vec[k];
                }
                if(temp != sum){
                    break;
                }
            }
            if(j == i){
                cout<<i<<endl;
                return 0;
            }
        }
    }
}

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

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