The Gift – solution CodinGame en C
On trie les budgets par ordre croissant. Si leur somme est inférieure au prix du cadeau, on affiche IMPOSSIBLE ; sinon on parcourt les participants du plus pauvre au plus riche et chacun paie min(budget, prix restant / participants restants) en division entière, en retranchant chaque paiement du prix. Cela minimise la plus grosse contribution et produit les montants déjà triés par ordre croissant, en O(n log n) à cause du tri.
L'énoncé
N amis veulent acheter un cadeau qui coûte C. Chacun a un budget personnel B qu'il ne peut pas dépasser. Il faut décider combien chacun paie pour que le total fasse exactement C et que la répartition soit la plus équitable possible : le paiement le plus élevé doit être le plus petit possible, puis le deuxième plus élevé, et ainsi de suite. Les montants sont entiers.
On affiche chaque contribution sur sa propre ligne par ordre croissant, ou IMPOSSIBLE si tous les budgets réunis ne couvrent pas le prix. Il peut y avoir jusqu'à environ 2 000 participants et le prix tient largement dans un entier 32 bits.
La démarche, étape par étape
- Vérifier d'abord la faisabilitéOn additionne tous les budgets. Si la somme est inférieure à C, aucune répartition n'existe et la réponse est IMPOSSIBLE. Utilisez un type 64 bits si votre langage peut déborder avec de gros budgets.
- Trier les budgets par ordre croissantLes participants les plus pauvres sont les seuls à risquer de ne pas pouvoir payer une part équitable, donc il faut les traiter en premier. Le tri produit aussi gratuitement la sortie croissante demandée.
- Part équitable de ce qui restePour le participant i (à partir de 0), il reste N - i personnes. Sa part équitable est restant / (N - i) en division entière. La personne paie cette part, ou tout son budget s'il est plus petit.
- Mettre à jour et recommencerOn retranche le paiement du prix restant et on passe à la personne suivante. Comme la dernière personne divise par 1, elle absorbe le reste éventuel laissé par la division entière, ce qui garde les plus gros paiements en fin de liste.
Complexité
O(n log n)O(n)Le tri domine ; la répartition elle-même est un seul passage avec un travail constant par personne.
Code de la solution
The Gift – C
Le code C trie avec qsort et un comparateur à trois issues, et calcule chaque contribution avec un ternaire sur prix/(N-i). Les paiements sont affichés au fil du calcul, ce qui est déjà croissant puisque le plafond et la part équitable augmentent tous deux le long de la liste triée.
#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;
}
Erreurs fréquentes
- Diviser C une seule fois puis plafonnerCalculer C / N une fois et plafonner les participants pauvres laisse une partie du prix non couverte. La part impayée doit être redistribuée, d'où le recalcul de la part à partir du prix restant à chaque étape.
- Mettre le reste sur les mauvaises personnesAvec C = 10 et trois personnes aux gros budgets, la sortie correcte est 3, 3, 4. Donner l'unité supplémentaire à la première personne (4, 3, 3) n'est pas croissant et échoue aux tests.
- Traiter dans l'ordre d'entréeSi un participant riche est traité avant un pauvre, le riche paie trop peu et le pauvre ne peut pas couvrir le reste. Triez toujours d'abord.
- Débordement d'entier sur le totalBeaucoup de budgets proches de la limite haute peuvent dépasser 32 bits une fois sommés dans certains langages. Un accumulateur long évite un faux IMPOSSIBLE.
Pour aller plus loin
Pourquoi ce glouton est-il optimal ? Supposons que la personne la plus pauvre puisse payer la part équitable restant/k. Alors tous les autres le peuvent aussi, puisque les budgets sont triés, et toute répartition qui fait payer moins que la part à quelqu'un en pousse forcément un autre au-dessus, ce qui augmente le maximum. Si la plus pauvre ne peut pas payer la part, alors dans toute répartition optimale elle doit payer tout son budget : payer moins reporterait la charge sur d'autres qui paient déjà au moins autant. Dans les deux cas la première décision est forcée, et la suite est le même problème avec une personne de moins et un prix plus petit. Cet argument par récurrence explique aussi pourquoi la sortie est automatiquement triée : chaque personne paie au plus ce que paiera la suivante.
Questions fréquentes
Quand The Gift doit-il afficher IMPOSSIBLE ?
Uniquement quand la somme de tous les budgets est strictement inférieure au prix du cadeau. Si la somme égale le prix, chacun paie l'intégralité de son budget.
Faut-il trier la sortie séparément ?
Non. Traiter les budgets par ordre croissant avec la règle de la part équitable produit des contributions déjà non décroissantes.
Existe-t-il une solution par recherche binaire ?
Oui : on cherche par dichotomie le plafond M tel que la somme des min(budget, M) atteigne C, puis on distribue les unités restantes aux plus riches. Cela marche mais demande plus de code que le glouton en un passage.