Robert Eisele
Engineer, Systems Architect and DBA

Codingame: The Gift

Original Problem

The Goal

The Oods want to offer a present to one of them. The thing is, they all have different budgets to invest in this present. Of course, their unique wish is to find the fairest method that will determine the maximum budget that each Ood can afford. The Oods have been discussing this issue for days, and up until now, they have not managed to find a totally satisfactory solution.

The Doctor decides to give a helping hand by creating a program. His idea is to check if the Oods have enough money to buy the present, and if so, to calculate how much each Ood should pay, according to their respective budget limit.

Rules

The Doctor has in hand the list of maximum budgets for each Ood. The Doctor's aim is to share the cost very precisely. To respect the Oods democratic values and to select the best solution, the Doctor decides that:
  • no Ood can pay more than his maximum budget
  • the optimal solution is the one for which the highest contribution is minimal
  • if there are several optimal solutions, then the best solution is the one for which the highest second contribution is minimal, and so on and so forth...
Moreover, to facilitate the calculations, the Doctor wants each financial participation to be an integer of the local currency (nobody should give any cents).

Examples

For example, the Oods wish to buy a gift that cost 100. The first Ood has a budget of 3, the second has a budget of 45 and the third has a budget of 100.

In that case:

BudgetSolution
33
4545
10052

Second example: they still wish to buy a gift that costs 100 but the second Ood has a budget of 100 this time.

In that case:

BudgetSolution
33
10048
10049

Game Input

Input

Line 1: the number N of participants

Line 2: the price C of the gift

N following lines: the list of budgets B of participants.

Output
  • If it is possible to buy the present : N lines, each containing the contribution of a participant. The list is sorted in ascending order.
  • Otherwise the word IMPOSSIBLE.
Constraints
0 < N ≤ 2000
0 ≤ C ≤ 1000000000
0 ≤ B ≤ 1000000000

Solution

If the sum of all budgets is less than the actual cost, it is impossible to buy the gift. The idea of splitting the cost among the Oods if it's possible, is calculating a fair share and see if the Ood with the smallest budget can afford this. If it's possible this Ood will pay the share, otherwise he will pay his budget limit. We now reduce the total cost by the amount of money the first Ood payed. We now share the remaining cost among the remaining Oods. We continue doing this by choosing the Ood with the smallest budget again and start the algorithm all over again. It's possible to implement this algorithm in just a few lines of code:

<?php

fscanf(STDIN, "%d", $N);
fscanf(STDIN, "%d", $C);
$budget = array();
$sum = 0;

for ($i = 0; $i < $N; $i++) {
    fscanf(STDIN, "%d", $B);
    $budget[] = $B;
    $sum+= $B;
}

if ($sum < $C) {
    echo("IMPOSSIBLE\n");
} else {
    
    sort($budget);
    
    for ($i = 0; $i < $N; $i++) {
        
        $p = floor($C / ($N - $i));
        $m = min($budget[$i], $p);

        echo $m, "\n";
        $C-= $m;
    }
}

Go to overview