پاسخ سوال دسته به دسته کوئرا

پاسخ سوال دسته به دسته کوئرا

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

پاسخ سوال دسته به دسته کوئرا

محمدجواد که پشت‌کار بالایی دارد، مسئول برگزاری جام حذفی برنامه‌نویسی شده است. همان‌طور که از اسمش پیداست این مسابقات قوانین عجیب و غریبی هم دارند. در این مسابقات 2^n تیم شرکت می‌کنند که تیم iم‌، به اندازه‌یp_i​ قدرت کدزدن دارد. در هر مرحله از مسابقه محمدجواد تیم‌های حاضر را به دو دسته تقسیم می‌کند که دسته‌ی اول به ترتیب نصفه‌ی اول تیم‌های باقی‌مانده هستند و دسته‌ی دوم نصفه‌ی دوم. سپس محمدجواد به هر دسته پروژه‌ای می‌دهد و تصمیم می‌گیرد که با یک دسته خداحافظی کرده و با دسته‌ی دیگر ادامه دهد و به پرقدرت ترین تیم دسته‌ی از دست رفته به اندازه‌ی قدرتش جایزه دهد. محمدجواد دوست دارد بیش‌ترین جایزه‌ی ممکن را به شرکت کنندگان بدهد. برای همین از شما کمک می‌خواهد که به او بگویید چه مقدار پول باید از سرمایه‌گذار دریافت کند. دقت کنید که محمدجواد به تیم آخر نیز جایزه خواهد داد. به عنوان مثال اگر ۸ تیم قرار بگیرد که قدرت هایشان برابر 1 6 1 7 1 8 1 4 می‌شود، محمد جواد می‌تواند در مرحله‌ی اول با ۴ تیم اول(تیم‌های با شماره ۱ و ۲ و ۳ و ۴) خداحافظی کرده و به اندازه ۸تا به تیم شماره ۳ جایزه دهد سپس با ۲ تیم دسته‌ی دوم (تیم‌های با شماره ۷ و ۸) خداحافظی کرده و ۶تا به تیم شماره‌ ۷ جایزه دهد و در مرحله ی بعد با تیم شماره ۵ خداحافظی کرده و ۷تا به او جایزه بدهد و در انتها به تیم شماره ۶ نیز ۱ی جایزه دهد که در مجموع می‌شود ۸ +‌ ۶ + ۷ + ۱ = ۲۲ او می‌تواند به جای روش بالا به ترتیب با ۴ تیم دوم خداحافظی کرده سپس با تیم سه و چهار و بعد از آن با تیم یک خداحافظی کند. که در این صورت باید به اندازه ۷ +‌ ۸ +‌ ۴ +‌ ۱ = ۲۰ تا جایزه دهد که یعنی روش اول بهتر بود.

ورودی سوال دسته به دسته

در سطر اول ورودی n آمده است که نشان‌دهنده‌ی تعداد مراحل است. در خط بعدی 2^n عدد آمده است که عدد iم نشان‌دهنده‌ی p_i​ است.

$$1\le n\le 17$$

1 ≤ pi​ ≤ 1000000000

خروجی سوال دسته به دسته

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

حل سوال دسته به دسته

#include <bits/stdc++.h> 
using namespace std;
 
int team[1<<17]; // 1<<17 is equal to 2^17, maximum of team counts
long long calculate(int l, int r)
{
    if(l == r) // if l==r then this is last team so we should return power of this team
        return team[l];
    int mid = (l+r)/2;
    long long c1 = calculate(l, mid); //maximum possibe of gift if we choose left
    long long c2 = calculate(mid+1, r); //maximum possibe of gift if we choose right
    int max1 = *max_element(team+mid+1, team+r+1); // maximum power of right(for choosing left)
    int max2 = *max_element(team+l, team+mid+1); // maximum power of left(for choosing right)
    
    return max(c1 + max1, c2 + max2); // return maximum of choosing left or right
}
 
int main()
{
    int n;
    cin >> n;
    for(int i=0; i<(1<<n); i++) // get all teams power values
        cin >> team[i];
    
    cout << calculate(0, (1<<n)-1) << endl;
    return 0;
}

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

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

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