×

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


# COMPLEXITY

$O(Nlog(N) + Q)$

# SIMILIAR PROBLEMS

Ruspa And Game

Query Over Matrix

Minimum Maximum

This question is marked "community wiki".

1.7k11630
accept rate: 11%

19.3k348495534

 0 Can someone explain , why are we choosing (N / (k+1) ) coins answered 24 Jan '16, 20:22 4★bhishma 296●7 accept rate: 11%
 0 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) answered 26 Sep '16, 02:29 1 accept rate: 0%
 0 There is a problem with the editorial code cin>>n>>q; q is at the end of the arr input answered 15 Oct '16, 17:53 3★p1y1_3 1 accept rate: 0%
 0 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<
 0 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 answered 21 Apr '17, 11:30 1 accept rate: 0%
 0 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 answered 10 Oct '17, 21:06 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,005
×3,394
×1,878
×742
×167
×52
×6

question asked: 17 Nov '15, 03:14

question was seen: 4,167 times

last updated: 10 Oct '17, 21:06