Problem link : Money Heist
Author : Pratyush
Tester: Prajwal
Difficulty: Easy-Medium
Prerequisite: Priority Queue
Problem:
Your task is to find the maximum number of coins that can be grabbed in K minutes by choosing the chest with the maximum number of coins every minute and not choosing the same chest more than B times. You also have to display the chest number chosen every minute.
Hint 1
Take a priority queue where each element has two fields.
First field stores the number of coins.
Second Field stores the the chest number.
Hint 2
Iterate a loop for K times, each time taking the first element of the priority queue and perform operations on it.
Explanation
You have to insert the number of coins and the index number of the chest in the priority queue. The index number stored should be negative as it is mentioned in the question that if multiple chests have the same number of coins then the chest with the lower index should be chosen, so by adding the negative index we can get the chest with the lower index higher up in the priority queue.
Then you have the take the first element in the priority queue and calculate the 1/3rd (ceil value) and decrease that value from the number of coins from that chest as well as add that value to the answer. Also store the index number of the chest selected from the priority queue in a vector. Now remove that element from the priority queue update the array which stores the count for the number of times a chest is chosen so that you can’t choose the chest for more than B times and now push the updated element back in the priority queue.
Problem Setter's Solution
#include <bits/stdc++.h>
#define ll long long
#define test unsigned int t;cin >> t;while(t--)
#define fr(n) for(i = 0 ; i < n ; i++)
#define fre(n) for(i = 1 ; i <= n ; i++)
#define pn(x) cout << x <<"\n";
#define ln cout << "\n";
#define ps(x) cout << x <<" ";
#define pb push_back
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
int main()
{
fastio
test
{
ll n,i,k,ans=0,a,b;
cin >> n >> k >> b;
priority_queue<vector<ll>> pr;
vector<ll> chest;
ll freq[n+1]={0};
fr(n)
{
cin >> a;
pr.push({a,-i-1});
}
while(k-- && pr.size() != 0)
{
ll in = pr.top()[1];
chest.pb(-in);
a = pr.top()[0];
ans+=(ll)ceil(a/3.0);
a-=(ll)ceil(a/3.0);
i = freq[-in];
pr.pop();
if(a > 0 && i+1 < b)
{
freq[-in]++;
pr.push({a,in});
}
}
ps(ans)
pn(chest.size())
fr(chest.size()) ps(chest[i]);
ln
}
return 0;
}
