Category: Software Development

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.