Day 13 : Tasks

Date : 13 December , 2020

Technical

Given the following prefix expression: * + 3 + 3 ↑ 3 + 3 3 3 What is the value of the prefix expression? a) 2178 b) 2199 c) 2205 d) 2232

We have prefix expression: 3 + 3 ↑ 3 + 3 3 3 = * + 3 + 3 ↑ 3 6 3 = * + 3 + 3 729 3 = * + 3 732 3 = * 735 3 = 2205 So, option (C) is correct

Coding

Given N bags, each bag contains Bi chocolates. There are a kid and a magician. In one unit of time, the kid chooses random bag i, eats Bi chocolates, then the magician fills the ith bag with floor(Bi/2) chocolates. Find the maximum number of chocolates that kid can eat in A units of time. NOTE: floor() function returns the largest integer less than or equal to a given number. Return your answer modulo 10^9+7

Input Format First argument is an integer A. Second argument is an integer array B of size N.

Output Format Return an integer denoting the maximum number of chocolates that kid can eat in A units of time.

Example Input Input 1: A = 3 B = [6, 5] Input 2: A = 5 B = [2, 4, 6, 8, 10]

Example Output Output 1: 14 Output 2: 33

Example Explanation Explanation 1: At t = 1 kid eats 6 chocolates from bag 0, and the bag gets filled by 3 chocolates. At t = 2 kid eats 5 chocolates from bag 1, and the bag gets filled by 2 chocolates. At t = 3 kid eats 3 chocolates from bag 0, and the bag gets filled by 1 chocolate. so, total number of chocolates eaten are 6 + 5 + 3 = 14

Solution

long long int mod = 1000000007;
int Solution::nchoc(int A, vector<int> &B) {
int N = B.size();
int K = A;
long long int ans = 0;
priority_queue<int> heap(B.begin(),B.end());
while(K--){
long long int max_elem = heap.top();
ans += max_elem;
ans = ans % mod;
heap.pop();
heap.push((int)(max_elem/2));
}
return ans;
}