CodinGame - Solution in Javascript to Dr Who - The Gift Challenge

Print

This is a Javascript implementation of a solution to the CodingCame Dr Who - The Gift challenge. It follows in a series of posts on the feasibility of Javascript solutions to CodinGame problems.

For the C# version of the same solution to this problem, see here.


/**
 * Auto-generated code below aims at helping you parse
 * the standard input according to the problem statement.
 **/

var N = parseInt(readline());
var C = parseInt(readline());

var B = [];                         // holds the budget for each ood
var totalBudget = 0;                // total budget available from all oods

for (var i = 0; i < N; i++) {
    B[i] = parseInt(readline());
    totalBudget += B[i];
}


if(totalBudget < C) 
{
    // the total budget is not enough to cover the cost of the gift
    print('IMPOSSIBLE');
    
}
else
{
        
    // if we have enough money, let's see how to best distribute the cost
    
    var oodsLeft = N;       // keeps track of how many oods still have monely left
    var P = [];             // keeps track of how much each ood will pay
    
    for(var i = 0; i < N; i++)
        P[i] = 0;
            
    // 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)
    {
        var fair = parseInt(C / oodsLeft);    // what would be an ideal fair split given # of oods that still have money
        
        for(var i = N-1; i >= 0; i--)
        {
            if(B[i] == 0) continue;     // this ood is out of money, skip him..
            
            var pays = (B[i] < fair) ? 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(var 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..
    P.sort(function(a,b) { 
        return a-b; 
    });
        
    // we're done (just print out each payment)
    for(var i = 0; i < N; i++)
        print(P[i]);
}

The problem statement can be found on the CodinGame website.

Also, you can find the implementation for the Conway Sequence problem 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