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

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

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

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

 

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

 

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

در اداره مالیات n مالیات‌چی وجود دارد.

مالیات‌چی i ام می‌تواند از  نفر خاص در شهر مالیات بگیرد.

متاسفانه به علت کمبود بودجه اداره مالیات، ما برای سال بعد فقط می‌توانیم تا از مالیات‌چی‌ها را نگه داریم، حالا از شما می‌خواهیم به رییس اداره مالیات بگویید در صورتی که به بهترین شکل این  نفر را انتخاب کند حداکثر از چند نفر می‌تواند مالیات بگیرد.

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

مثلا مالیات چی اول و دوم هر کدام می‌توانند به ترتیب از ۷ و ۸ نفر در شهر مالیات بگیرند اما ۳ نفر از این افراد مشترک است، پس چنانچه بخواهیم دو نفر مالیات‌چی نگه داریم و این دو نفر را انتخاب کنیم ما از ۱۲ نفر می‌توانیم مالیات بگیریم نه از ۱۵ نفر.

برای فهم بهتر سوال بخش ورودی را بخوانید.

 

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

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

سپس در خط بعد n عدد که  هاست به شما داده می‌شود.

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

** دقت کنید که اشتراک‌هایی که به شما داده می‌شوند از هم جدا و کاملا مستقل هستند؛ یعنی مثلا اگر مالیاتچی‌های ۱ و ۲ و ۳ در ۵ نفر و مالیاتچی‌های ۱ و ۲ در ۴ نفر با هم اشتراک داشته باشند، طبیعتا این ۴ نفر کاملا مستقل از آن ۵ نفر بوده و هیچ اشتراکی ندارند. **

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

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

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

 

حل سوال اداره مالیات (به زبان برنامه نویسی سی پلاس پلاس)

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

 

 

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

 

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

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

موفق باشید.

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