Yet another puzzle created by Clive Fraser - many thanks!
A group of scientists are studying the growth of various micro-organisms. The organisms are allowed to grow in a special growth medium which covers the base of a large square tray. The tray is divided into a large number of unit squares but the micro-organisms are free to spread across the boundaries of these squares. The number of micro-organisms in one of the unit squares is usually too large to be counted accurately by a person. Fortunately there is a special device which uses a camera and some AI software to give accurate counts for each of the unit squares.
The tray is a square of side N units. Investigation of the micro-organisms involves the use of a smaller
square (called a Quadrat) of side Q units. In larger scale sampling (usually conducted outdoors) the
quadrat is a solid frame. In this example it is simply a means of referring to any Q x Q group of unit squares
in the growth tray. The organism counts for each unit square are used as the basis for a large number of
statistical calculations to provide information about the way in which the organisms multiply and spread.
One of the statistical calculations involves the unit squares within the quadrat. We find the smallest and largest organism counts for the group of squares within the quadrat. We then take the difference between these two. We would like to know the average for this value, taken over all possible positions of the quadrat in the tray. In order to find this average we first need to find the total and then to divide this by the number of positions for the quadrat. As the division is subject to rounding errors you are asked to stop after finding the total and to give this as the answer to the problem.
We need to have access to the organism counts for each of the unit squares. We will use a random number
generator to create them, as follows. The
Linear Congruential Generator has been used before in
CodeAbbey 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 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.
As an example, consider the following small version of the problem. (The actual problem will be much larger.)
We will take N = 4 and Q = 2. This means that the tray has size 4 x 4 and contains 16 unit squares.
The quadrat has size 2 x 2 and covers 4 of the unit squares. 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 16 random numbers needed to create the
organism counts. This sequence is 700001, 1819434, 840897, 1603084, 1034921, 1959835, ..., 631425.
We will use these numbers to fill up the squares in the tray, row by row starting from the top, and from left
to right in each row. The following table shows how the grid of squares is filled up.
700001 1819434 840897 1603084
1034921 1959835 404272 244507
452828 880237 234863 355586
1648096 93571 395716 631425
The quadrat covers 4 of these squares. If it is placed level with the top row of the grid it can be placed in
3 different positions, at the left side, in the middle or at the right side. It can also be placed in 3
different positions going down the grid. So there are 9 possible positions for the quadrat.
The following three tables show the smallest values in each quadrat (left table), the largest values in each
quadrat (middle table) and the differences (right table).
700001 404272 244507 1959835 1959835 1603084 1259834 1555563 1358577
452828 234863 234863 1959835 1959835 404272 1507007 1724972 169409
93571 93571 234863 1648096 880237 631425 1554525 786666 396562
We require the total of the differences. This is the total of the 9 values in the right hand table. So the
required total is 10313115.
In the actual problem the value of N will not exceed 800 and the value of Q will be about half of that.
Note that this results in approximately 160000 possible positions for the quadrat. You are encouraged to look
for an efficient solution. The Setter program (using normal Python) finds the required answer in less than 1 second.
Input/Output description: The only line of the input data will contain three space-separated integers,
the random seed X(0) followed by the tray size N and the Quadrat size Q. You are asked to calculate the
total of differences, over all of the quadrat positions, as described above. Give this total as your answer.
Example:
input:
0 4 2
answer:
10313115