Many thanks to Clive Fraser for this problem!
As a reward for services rendered the king is going to give you a large number of diamonds. However, there is a
catch! You will only be allowed to keep them if you solve his puzzle correctly. The diamonds are placed in each
square of a large rectangular grid. Each square on the grid contains a large number of diamonds. The grid is
W squares wide (from west to east) and H squares high (from north to south). You must collect the diamonds
according to the following rules.
You may choose any of the 4 corner squares of the grid as your starting point (or choose from just 2
squares if the grid is only 1 square wide). You make moves from square to square. A single move takes you to
any one of the adjacent 4 squares (north, south, east or west) except when the current square is on the
border of the grid, when there will be only 1, 2 or 3 possible directions in which to move.
You must plan a route, from your chosen starting corner, which allows you to collect as many diamonds as
possible and to return to the starting point again. You are not allowed to enter the same square for a second
time, except for your final move which must be a return to the starting square. In addition you are only
allowed to collect diamonds from squares which are visited on odd-numbered moves. If any of the rules are broken
you will not be able to keep any of the diamonds. The final catch is that you are required to find a route
which maximises the number of diamonds that you collect. If you collect a number smaller than this, you will
lose them all!
Your task is to determine the maximum number of diamonds which can be collected from a given grid. We will use a
random number generator to create the number of diamonds in each square, 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 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.
In order to provide an example to illustrate the problem we will choose a small grid of size W = 3 and H = 2,
which contains only 6 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 6 random numbers needed to create the numbers of diamonds in each square.
This sequence is 700001, 1819434, 840897, 1603084, 1034921, 1959835. We will fill the grid row by
row from north to south and, within a row, from west to east. The grid, with the random numbers included, is
shown below.
700001 1819434 840897
1603084 1034921 1959835
One possible sequence which maximises the number of diamonds collected is:
840897 --> 1819434 --> 700001 --> 1603084 --> 1034921 --> 1959835 --> 840897
There are 6 moves in total. Diamonds can only be collected from the squares moved into on the odd moves
(1, 3 and 5). So the number of diamonds collected is 1819434 + 1603084 + 1959835 = 5382353.
Input/Output description: The first line of the input data will be a single integer N for the number of
puzzles to be solved. N lines will follow. Each of these contains three space-separated integers X(0), W
and H. X(0) is the seed for the random number generator. W and H are the dimensions of the grid.
For each puzzle you need to find the maximum number of diamonds that can be collected. Give all answers,
separated by spaces, as a single string.
Example:
input:
2
0 3 2
836799 40 47
answer:
5382353 993490644