The Gift – CodinGame solution in C
Sort the budgets in ascending order. If their sum is below the gift price, print IMPOSSIBLE; otherwise go through participants from poorest to richest and have each pay min(budget, remaining price / remaining participants) with integer division, subtracting each payment from the price. This minimises the largest contribution and prints the amounts already in ascending order.
The problem
N friends want to buy a gift costing C. Each one has a personal budget B and cannot pay more than that. You must decide how much each person pays so that the total equals C exactly and the split is as even as possible: the highest payment must be as small as possible, then the second highest, and so on. Amounts are integers.
Print each contribution on its own line in ascending order, or IMPOSSIBLE if all budgets together cannot cover the price. There can be up to about 2,000 participants and the price fits comfortably in a 32-bit integer.
Approach, step by step
- Check feasibility firstAdd all budgets. If the sum is less than C, no split exists and the answer is IMPOSSIBLE. Use a 64-bit type if your language could overflow with large budgets.
- Sort budgets ascendingPoorer participants are the only ones who may not be able to pay a fair share, so they must be handled first. Sorting also produces the required ascending output for free.
- Fair share of what is leftFor participant i (0-based) there are N - i people left. Their fair share is remaining / (N - i) using integer division. The person pays that share, or their whole budget if it is smaller.
- Update and repeatSubtract the payment from the remaining price and move to the next person. Because the last person divides by 1, they absorb any remainder left by integer division, which keeps the largest payments at the end of the list.
Complexity
O(n log n)O(n)Sorting dominates; the distribution itself is a single pass with constant work per person.
Solution code
The Gift – C
The C code sorts with qsort and a three-way comparator, and computes each contribution with a ternary on price/(N-i). Payments are printed as they are computed, which is already ascending because both the cap and the fair share grow along the sorted list.
#include <stdlib.h>
#include <stdio.h>
int cmp (const void * a, const void * b){
int aa = *(int*)a;
int bb = *(int*)b;
return aa<bb?-1:aa>bb?1:0;
}
int main(int argc, char **argv)
{
// Read input : number of participants, price of the gift, budgets
int N, price;
scanf("%d\n%d\n", &N, &price);
int budgets[N];
int totalBudget = 0;
for (int i = 0; i < N; i++) {
scanf("%d\n", &budgets[i]);
totalBudget += budgets[i];
}
if (totalBudget < price)
printf("IMPOSSIBLE\n");
else {
/* sorts budgets, then starting from the lower budgets
each particpant contributes (price left) / (number of participants left)
or if he hasn't enough money, everything he has*/
qsort(budgets, N , sizeof(int), cmp);
int contribution;
for (int i = 0; i < N; i++) {
contribution = (budgets[i] >= price/(N-i)) ? price/(N-i) : budgets[i] ;
printf("%d\n", contribution);
price -= contribution;
}
}
return EXIT_SUCCESS;
}
Common mistakes
- Splitting C evenly once and cappingComputing C / N once and capping poor participants leaves money uncovered. The unpaid part must be redistributed, which is why the share is recomputed from the remaining price at each step.
- Putting the remainder on the wrong peopleWith C = 10 and three people with large budgets, the correct output is 3, 3, 4. Giving the extra unit to the first person (4, 3, 3) is not ascending and fails the tests.
- Processing in input orderIf a rich participant is handled before a poor one, the rich one pays too little and the poor one cannot cover the rest. Always sort first.
- Integer overflow on the totalMany budgets near the upper limit can exceed 32 bits when summed in some languages. A long accumulator avoids a false IMPOSSIBLE.
Going further
Why is this greedy optimal? Suppose the poorest person can afford the fair share remaining/k. Then everyone else can too, since budgets are sorted, and any distribution that makes someone pay less than the share forces someone else above it, increasing the maximum. If the poorest cannot afford the share, then in any optimal split they must pay their entire budget: paying less would push the burden onto others who already pay at least as much. Either way the first decision is forced, and the rest is the same problem with one fewer person and a smaller price. That inductive argument is also why the output is automatically sorted: each person pays at most what the next person will pay.
FAQ
When should The Gift print IMPOSSIBLE?
Only when the sum of all budgets is strictly smaller than the gift price. If the sum equals the price, everyone pays their full budget.
Do I need to sort the output separately?
No. Processing budgets in ascending order with the fair-share rule produces contributions that are already non-decreasing.
Is there a binary search solution?
Yes: binary search the cap M such that the sum of min(budget, M) reaches C, then distribute the leftover units to the richest. It works but is more code than the one-pass greedy.