The Goal
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
- 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...
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:
| Budget | Solution |
|---|---|
| 3 | 3 |
| 45 | 45 |
| 100 | 52 |
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:
| Budget | Solution |
|---|---|
| 3 | 3 |
| 100 | 48 |
| 100 | 49 |
Game 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.
- 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.
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;
}
}