Our thanks to Clive Fraser for this problem!
A large toy company wants to include a hand-crafted toy as part of its Christmas range. The company can produce most of the toy in their own workshops but will need to go to specialist craftspeople for two of the essential components. The specialist craftspeople are usually individuals, working in small premises and capable of creating only a small number of the required components. Fortunately, the company know a large number of craftspeople who are capable of doing the necessary work. All of them can make both components but will be more productive if they can make just one of them.
We will refer to the two required components as A and B. The company asks each of the craftspeople to state the number of components A and B
that they can make in the required time, assuming that they are asked to make only component A or only component B. Once all of the replies
have been received, the production manager has a significant problem to solve. The company wants to maximise the number of toys that can be
completed, so the manager must now determine which of the two components each of the craftspeople will be asked to make. It is then possible to
determine the maximum number of toys that can be completed.
Since there is a great deal of data in this problem, we will use a random number generator to create it, as follows. The
Linear Congruential Generator 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. However, these are much too large for this problem.
For each random value X(n) we will create the required number of components R(n) using the formula:
R(n) = 20 + X(n) % 100
It should be obvious that the values of R(n) will vary between 20 and 119 inclusive. These values will be the number of components which
each craftsperson is able to make. We will use a small example, with just 5 craftspeople, to illustrate the problem. Each of the craftspeople
will state the numbers of components A and B that they are able to make. This means that we need 10 random values to provide this data.
The first two values will be the number of components of A and B for craftsperson 1. The next two numbers are the numbers of components A
and B for craftsperson 2, and so on. If we take the random seed X(0) to be 0 (it will not be 0 in the actual problem) then we can
generate the 10 random numbers needed to create this data. The first 10 values generated for X(n) are
700001 1819434 840897 1603084 1034921 1959835 404272 244507 452828 880237
When we apply the formula for R(n) we get the following data for each of the craftspeople (numbered 1 to 5).
1 21 A 54 B
2 117 A 104 B
3 41 A 55 B
4 92 A 27 B
5 48 A 57 B
It is not difficult to see that we can assign craftspeople 2 and 4 to make component A and craftspeople 1, 3 and 5 to make component
B. This will generate 209 of the A components and 166 of the B components. This means that 166 of the special toys can be created.
You should be able to verify that we cannot do better than this.
The actual problem will use a different random seed and a much larger number of craftspeople (not more than 400). You will need to use the
random number generator described above to generate the numbers of A and B components for each craftsperson in turn. You must then decide
how to assign the work to each craftsperson in order to maximise the number of special toys that can be created. Only this final number is
required.
Input/Output description: The first and only line of the input data will contain 2 space separated integers. These are the random seed
X(0) and the number of craftspeople. Your answer is a single integer, the maximum number of special toys which can be created.
Example:
input:
0 5
answer:
166