TV Charity Fundraiser

This problem was created by Clive Fraser - many thanks for it!

A major annual event is used to raise money for a variety of different charities. In order to maximise the amount raised, the event is televised and has a substantial element of audience participation. A number of wealthy (and well-known) donors attend the event. Each donor submits a number to the organisers before the event. This number will be used to determine the actual donation to be made by the donor. At the start of the event a number of posters are placed around the wall of the venue. Each of these has the name and photograph of one of the donors, together with the number submitted by that donor.

In the centre of the venue there is a long table with a row of sealed boxes. Each box contains a card on which there is a multiplier. The multipliers are integers in the range 2 to 100 which have been chosen randomly for each box in turn, before the start of the event. There will be more boxes than there are donors. During the event, members of the audience who have paid for special tickets, are asked to come out, one at a time, to choose and open one of the sealed boxes. They then reveal the secret multiplier to the audience and the TV cameras. This process continues until we have the same number of multipliers as there are donors.

Next the people who have selected the multipliers work together to assign each multiplier to one of the donors. The actual donation made will be the number initially submitted by the donor (as a number of cents) multiplied by the assigned multiplier. The donors understand the system so know in advance that they will be required to pay between 2 and 100 times the amount of their initial submission. The people who assign the multipliers clearly want to raise the maximum amount for charity so they ensure that the largest multipliers are assigned to the donors who have made the largest initial submissions. You can assume that they do this in such a way that the total amount raised is a maximum.

In this problem you will be given details of the initial D donor submissions and the Mu multipliers placed in the sealed boxes. You are asked to calculate the expectation value of the total amount donated at the fundraiser.

The amount of data needed for this problem is large so we will use the Linear Congruential Generator to create it. This has been used before in Code Abbey problems. A random value X(n) is generated using the formula:

X(n) = (A * X(n-1) + C) % M

In this problem we will use the values A = 445, C = 700001 and M = 2097169. Note that % M means the remainder after dividing by the modulus value of M. The value X(n-1) is the previous random value to be generated by this expression. In order to generate the first random value X(1) we need to be given a value for X(0) which is called the seed for the generator. This value will be supplied as part of the data for the problem. The formula above creates a reasonable sequence of roughly random values, which we will use for the initial donor submissions.

In order to calculate the random multipliers (RM), we need to modify the value of X(n) by using the formula:

RM = X(n) % 99 + 2

It should be obvious that this gives a value for RM in the range 2 to 100 as required.

Consider a small example, where D = 3 and Mu = 5 (i.e. 3 donors and 5 boxes containing multiplier cards). If we take the random seed X(0) to be 0 (it will not be 0 in the actual problem) then we begin by generating the 3 initial donor submissions. The first 3 random numbers are: 700001, 1819434 and 840897 so we take these as the donor submissions.

Next we continue to generate 5 more random numbers for the 5 Multipliers. The next 5 random numbers are: 1603084, 1034921, 1959835, 404272 and 244507. We use these values with the formula to create the multiplier numbers 78, 76, 33, 57 and 78.

There are 5 sealed boxes. We need to select Multipliers from 3 of these. There are 10 ways of choosing 3 boxes from 5 so we must consider each of these in turn. If we label the boxes A, B, C, D and E (in the order in which the Multipliers were assigned) then the following table shows the calculations needed to find the total amount donated for each of the 10 ways of choosing the boxes.

A B C   78 x 1819434 + 76 x 840897 + 33 x 700001 = 228924057
A B D   78 x 1819434 + 76 x 840897 + 57 x 700001 = 245724081
A C D   78 x 1819434 + 57 x 840897 + 33 x 700001 = 212947014
B C D   76 x 1819434 + 57 x 840897 + 33 x 700001 = 209308146
A B E   78 x 1819434 + 78 x 840897 + 76 x 700001 = 260705894
A C E   78 x 1819434 + 78 x 840897 + 33 x 700001 = 230605851
B C E   78 x 1819434 + 76 x 840897 + 33 x 700001 = 228924057
A D E   78 x 1819434 + 78 x 840897 + 57 x 700001 = 247405875
B D E   78 x 1819434 + 76 x 840897 + 57 x 700001 = 245724081
C D E   78 x 1819434 + 57 x 840897 + 33 x 700001 = 212947014

The 3 selected boxes are shown in the left column. The corresponding multipliers are then matched with the donor submissions to achieve the largest possible total. The calculation for this is shown after the box selection. In order to calculate the expectation value of the amount donated we need to find the average of the 10 values shown above. This is 232321607 (rounded to the nearest whole cent). This is more than 2 million dollars, so the fundraiser has been a huge success.

Input/Output description: The only line of the input data will contain three space-separated integers D, Mu and S. These are the number of donors, the number of boxes containing multiplier cards and the Seed for the random number generator. Find the expectation value of the amount donated. Give this as a number of cents, rounded to the nearest integer.

Example 1:

input:
3 5 0

answer:
232321607

Example 2:

input:
12 25 919056

answer:
987978504

Example 3:

input:
1746 3190 860350

answer:
123648183605