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

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

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

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

در اداره مالیات n مالیات‌چی وجود دارد. مالیات‌چی i ام می‌تواند از ai​ نفر خاص در شهر مالیات بگیرد. متاسفانه به علت کمبود بودجه اداره مالیات، ما برای سال بعد فقط می‌توانیم $m$ تا از مالیات‌چی‌ها را نگه داریم، حالا از شما می‌خواهیم به رییس اداره مالیات بگویید در صورتی که به بهترین شکل این $m$ نفر را انتخاب کند حداکثر از چند نفر می‌تواند مالیات بگیرد. هم‌چنین می‌دانیم بعضی از اشخاصی که بعضی از مالیات‌چی‌ها می‌توانند از آن‌ها مالیات بگیرند مشترک هستند. مثلا مالیات چی اول و دوم هر کدام می‌توانند به ترتیب از ۷ و ۸ نفر در شهر مالیات بگیرند اما ۳ نفر از این افراد مشترک است، پس چنانچه بخواهیم دو نفر مالیات‌چی نگه داریم و این دو نفر را انتخاب کنیم ما از ۱۲ نفر می‌توانیم مالیات بگیریم نه از ۱۵ نفر. برای فهم بهتر سوال بخش ورودی را بخوانید.

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

در یک خط $n$ به شما داده می‌شود که تعداد مالیات‌چی‌هاست و سپس $m$ که تعداد مالیات‌چی‌هایی است که برای سال بعد. سپس در خط بعد $n$ عدد که ai​ هاست به شما داده می‌شود. در خط سوم $q$ به شما داده می‌شود و در q خط بعدی در هر خط ابتدا یک عدد ti​ می‌آید و سپس ti​ تا عدد که اندیس مالیات‌چی‌هاست و یک عدد ki​ که یعنی آن t_i تا مالیات‌چی در k_iki​ تا از مردم شهر با هم مشترک هستند. دقت کنید که اشتراک‌هایی که به شما داده می‌شوند از هم جدا و کاملا مستقل هستند؛ یعنی مثلا اگر مالیاتچی‌های ۱ و ۲ و ۳ در ۵ نفر و مالیاتچی‌های ۱ و ۲ در ۴ نفر با هم اشتراک داشته باشند، طبیعتا این ۴ نفر کاملا مستقل از آن ۵ نفر بوده و هیچ اشتراکی ندارند.

$$1\le m\le n\le 2$$

$$1\le q\le 10$$

2 ≤ ti​ ≤ n

1 ≤ ai​ ≤ 100

برای فهم بهتر توضیح نمونه ۱ را بخوانید.

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

در یک خط بیشینه‌ی تعداد نفراتی که می‌شود سال بعد از آن‌ها مالیات گرفت را چاپ کنید.

حل سوال اداره مالیات

#include <bits/stdc++.h> 
using namespace std;
#define ll long long
ll max(int a,ll b){ return max((ll)a,b);}
ll min(int a,ll b){ return min((ll)a,b);} 
ll min(ll a,int b){ return min(a,(ll)b);}
ll max(ll a,int b){ return max(a,(ll)b);}
 
int main()
{
    //int t; cin >> t; while(t--) solve();
    int n, m, q, t, a;
    cin >> n >> m;
    int chi[n];
    for(int i=0; i<n; i++) cin >> chi[i];
    
    cin >> q;
    vector<int> com[q];
    int ted[q];
    for(int i=0; i<q; i++)
    {
        cin >> t;
        com[i].resize(t);
        for(int j=0; j<t; j++)
            cin >> com[i][j];
        cin >> ted[i];
        for(int j=0; j<t; j++)
        {
            chi[com[i][j]-1] -= ted[i];
        }
    }
 
    long long cnt, maxi = -1;
    for(int i=0; i<(1<<n); i++)
    {
        if(__builtin_popcount(i) > m)
            continue;
        cnt = 0;
        for(int j=0; j<q; j++)
        {
            for(int k : com[j])
            {
                if( (1<<(k-1)) & i)
                {
                    cnt += ted[j];
                    break;
                }
            }
        }
 
        for(int j=0; j<n; j++)
        {
            if((1<<j) & i)
                cnt += chi[j];
        }
        maxi = max(cnt, maxi);
    }
    
    cout << maxi << endl;
    return 0;
}

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

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

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