CodinGame - Solution in C# to the Dr Who - The Gift Challenge

Print

This is a C# implementation of a solution to the CodingCame Dr Who - The Gift challenge. It follows in a series of posts on various solutions to CodinGame problems, that I initially started writing in JavaScript.

The article follows a series that I started with the goal of testing the feasibility of solving CodinGame challenges in Javascript.


using System;
using System.IO;
using System.Collections.Generic;


class Solution
{
    static void Main(String[] args)
    {
        int N = int.Parse(Console.ReadLine());
        int C = int.Parse(Console.ReadLine());
        
        int[] B = new int[N];               // holds the budget for each ood
        int totalBudget = 0;                // total buget for all oods combined
        
        for (int i = 0; i < N; i++)
        {
            B[i] = int.Parse(Console.ReadLine());
            totalBudget += B[i];
        }

        if(totalBudget < C) 
        {
            // the total budget is not enough to cover the cost of the gift
            Console.WriteLine("IMPOSSIBLE");
            return;
        }
        
        // if we have enough money, let's see how to best distribute the cost
        
        int oodsLeft = N;       // keeps track of how many oods still have monely left
        int[] P = new int[N];   // keeps track of how much each ood will pay
        
        // as long as we haven't yet covered the cost of the gift,
        //   and the cost requires more than 1 unit from each ood that still has money left
        //   .. keep splitting the cost ..
        while(C > oodsLeft)
        {
            int fair = C / oodsLeft;        // what would be an ideal fair split given # of oods that still have money
            
            for(int i = N-1; i >= 0; i--)
            {
                if(B[i] == 0) continue;     // this ood is out of money, skip him..
                
                int pays = Math.Min(B[i], fair);  // how much will this ood contribute?
                
                B[i] -= pays;                     // update his budget, after payment
                if(B[i] == 0) oodsLeft--;         // if he's out of money now, reduce # of ood left
                C -= pays;                        // also reduce the remainder cost 
                
                P[i] += pays;                     // and update the total payed by this ood
            }
        }
        
        // if we're here, and there is still some cost left, 
        //     it must only require unit money from each ood left
        for(int i = N-1; i >= 0 && C > 0; i--)
        {
            if(B[i] == 0) continue;  // this ood is out of money, skip'm..
            
            B[i]--;         // pays a unit..
            C--;            //   cost is reduced
            P[i]++;         //   and update his total amount to pay
        }
        
        // we have to list of how much each ood pays
        //     but we have to present it in ascending order, so sort it..
        Array.Sort(P);
        
        
        // we're done (just print out each payment)
        for(int i = 0; i < N; i++)
            Console.WriteLine(P[i]);
    }
}

The problem statement can be found on the CodinGame website.

You can also find the Javascript implementation for the Dr Who The Gift challenge here.

is the founder of Donaq, a software development consulting company with a focus on mobility. You can find Mike on Google+ and on LinkedIn.
Design copyright (c) Miky Dinescu