Many thanks to Mathias Kern aka gardengnome for this puzzle!
The pre-Christmas period is almost upon us. You are excited and decide to visit your old pal Santa Claus. To your surprise, you meet the Easter bunnies at his home, and you learn that they give Santa an Advent calendar every year. It's a truly ginormous calendar full of chocolate. No wonder that Santa has such a big belly, you think to yourself. But you also feel a tiny bit jealous, and the bunnies notice. 'Do not worry', they tell you, 'we have a challenge for you. Solve it and you can keep all the chocolate that you collect!'
The calendar doors are numbered from 1 to 999,999. Each door is associated with a seemingly random number
between 1 and 2,097,152 - the number of chocolate pieces behind the door. The bunnies give you a range of
doors, i.e. from a to b, and you have to find the k-th smallest number of chocolate pieces behind this
range of doors. Get the number right, open the corresponding door and keep the chocolate. But Santa is not
losing out, the chocolate is magically refilled every time. The bunnies play 9,999 rounds with you.
How many chocolate pieces can you collect overall?
Input: A single integer X0 that is used as the seed for the Linear Congruential Generator introduced in the
problem 25 - use A=445, C=700,001 and M=2,097,152.
First generate N=999,999 random values and add 1 to each one of them – the number of chocolate pieces
behind the doors. For X0=0, doors 1, 2 and 3 have 700,002, 1,821,951 and 1,967,080 chocolate
pieces behind them, respectively.
Then generate M=9,999 triplets a, b and k as follows: Generate 2 random values, transform them via
value % N + 1 to the range 1 ... N, and swap them around if the first is larger than the second. This gives
you the range [a, b] of doors. For k, generate a third random value and transform it via
value % (b-a+1) + 1 to the range 1 … (b-a+1) (there are b-a+1 doors in the range [a, b]).
Your task is to find the k-th smallest value in the range. For X0=0 and after all the random numbers for
the N=999,999 doors have been generated, the first three triplets (a, b, k) are (707106, 828546, 60281),
(547689, 554862, 144) and (213964, 945029, 113241), respectively.
Output: The sum of k-th smallest values across all M=9,999 rounds. For X0=0, the result is 10,174,856,758.