Coding Solution

The Gift – solution CodinGame en C

Moyengreedysortinginteger divisionMis à jour le
Réponse courte

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

  1. 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.
  2. 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.
  3. 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.
  4. 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é

TempsO(n log n)
MémoireO(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

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.

Puzzles similaires

★ 5,0 · 16 avis · 928 utilisateurs Ajouter à Chrome