Doctor Who - The Gift puzzle discussion


has anybody solved the gift puzzle? i compiled it with GNU using code::blocks and it works perfectly, but the tests either add a 0 in the beginning of the output or it says this


Pour le dernier niveau du cadeau, je n’arrivait pas à le faire. J’ai donc afficher toute les valeurs des budgets et j’ai eu à un moment de l’affichage un budget avec trois petits point et un trou
Est ce que c’est normal? Est ce que je dois verifier que ce soit bien un chiffre?


Quand tu affiches trop de choses, c’est coupé.
Un peu comme une citation de texte :
“blablabla blablabla […] blablabla blablabla”


J’arrive à passer tous les tests de l’ide et pourtant juste 33% des tests passent après soumission.
échecs sur les tests 2, 3, 5, 6, 7 et 8
J’utilise bash
Une idée ?


IMHO the sorting for this solution is a really bad thing because after you sort the result you don’t get which Ood pays what amount. This is really visible by a test case provided to the problem:


With this the first Ood would pay 1 from its 100 budget, the second Ood would pay 49 from its budget of 1, and the last Ood will pay 50 from its 60 budget. And this would violate the rules of the Doctor.


The actual canon plural of ‘Ood’ is ‘Ood’. One Ood, several Ood; they are the Ood.


The rule says that the optimal solution is the one for which the highest contribution is minimal. In your solution the highest contribution is 60 which is clearly greater than the 50 which the system expects.

Think about this way: they have budgets of 100, 1 and 60. The second Ood can only pay 1, that means the rest should pay 99 total. Now, they want to split this 99 in such a way that the highest contribution is minimal. It would be 49.5-49.5, but that’s not valid because the Doctor wants each financial participation to be an integer of the local currency (nobody should give any cents).So they split it 49-50,


If we also sort the input budgets then it can perfectly match the outputs


Is this really worth 100XP? Got it done in about 15mins maximum. From the first ood to the last, calculating the mean left.


It is nowhere mentioned that we can rearrange the elements in any order, as the results of the test cases I figured out that all outputs are in sorted order. Because if you re-arrange, there is problem that you cannot find out who will pay how much.
I think this should be mentioned in the problem or this should not be allowed.


quote from the statement:

If it is possible to buy the present : N lines, each containing the contribution of a participant. The list is sorted in ascending order.


Can you please give a better “Budget limit” case, because my code is passing your test, but fails when I submit ?


Found one:



Because now my program outputs:

And now I can look for the answer :slight_smile:


I agree with the comments saying it is an easy puzzle. I spent hours on some easy ones because they needed optimization and now I did it in only 5 minutes 100% succeeded. I would also like to point out that it talks about the “glutton algorithm”. I couldn’t find relevant informations and wrote a code with no glutton in it, with less code lines than the top rated solution. I sincerely think that puzzle needs to be upgraded.