 # AMR15D - Editorial

### Panel Members

Problem Setter: Suhash
Problem Tester:
Editorialist: Sunny Aggarwal
Russian Translator:
Mandarin Translator:
Vietnamese Translator:
Language Verifier:

Easy

### PREREQUISITES:

Basic Mathematics, Prefix Sum, Sorting, Dynamic Programming.

### PROBLEM:

Given a list of N coins of possibly different denominations. We can pay amount equivalent to any 1 coin and can acquire that coin. In addition once we have paid for a coin, we can choose atmost K more coins and can acquire those for free. What is the minimum amount required to acquire all the N coins for a given K ?

Note that a coin can be acquired only once.

### EXPLANATION

It is easy to notice that at a cost of 1 coin, we can acquire at most K+1 coins. Therefore, in order to acquire all the N coins we will be choosing \lceil N/(K+1)\rceil coins and the cost of choosing coins will be minimum if we choose smallest \lceil N/(K+1)\rceil coins. Smallest \lceil N/(K+1)\rceil coins can be found by simply sorting all the N values in increasing order.

C++ code:

```int main() {
int n, k;
cin >> n >> k;
int arr[n];
for(int i=0; i<=n-1; i++) {
cin >> arr[i];
}
sort(arr, arr+n);
int coins_needed = ceil(1.0*n/(k+1));
int ans = 0;
for(int i=0; i<=coins_needed-1; i++) {
ans += arr[i];
}
cout << ans << "\n";
return 0;
}
```

As we are asked to find the above answer for many different values of K, we have to compute it fast. For the purpose to serve, we can maintain a prefix sum array after sorting all the N values and can answer queries easily.

C++ code:

```int main() {
int n, q, k;
cin >> n >> q;
int arr[n];
for(int i=0; i<=n-1; i++) {
cin >> arr[i];
}
sort(arr, arr+n);
for(int i=1; i<=n-1; i++) {
arr[i] += arr[i-1];
}
while( q-- ) {
cin >> k;
int coins_needed = ceil(1.0*n/(k+1));
int ans = arr[coins_needed-1];
cout << ans << "\n";
}
return 0;
}
```

O(Nlog(N) + Q)

### SIMILIAR PROBLEMS

Ruspa And Game

Query Over Matrix

Minimum Maximum

2 Likes

Can someone explain , why are we choosing (N / (k+1) ) coins

Hello bhishma,

At a cost of 1 coin we can acquire at most K (free coins) + 1 (paid coin).
that is

for getting K+ x coins we need to pay x (cost)

so for getting N coins we need to pay

N * x/(K + x)

There is a problem with the editorial code

cin>>n>>q;

q is at the end of the arr input

https://www.codechef.com/viewsolution/11895664 is giving wrong ans and https://www.codechef.com/viewsolution/11895767 is accepted . the only line i changed was from cout<<res[n-k-1]<<endl; to ul c_n = ceil(1.0*n/(k+1));
cout<<res[c_n-1]<<endl;

can’t understand the question…what if i give n=16 and values will be 22,21,18,17,15,13,12,11,9,8,7,5,4,3,2,1 and k=22,21,7,6,10,8,2,3,23 ,please expalin for these

in the given question it is given that it can loot at most k houses.
so how can we claim that–It is easy to notice that at a cost of 1 coin, we can acquire at most K+1 coins.
if k=2 then we can at cost of 1 coin then we should be able to acquire at most K+1=3 coins.
which is contradicting the given example

//