After the lesson on arithmetic progressions, the teacher gave Peter homework: a sheet of paper with numbers
written in some cells of a R x C grid. Some of the cells were empty. Peter's task is to create an arithmetic
rectangle by filling in the missing numbers. In an arithmetic rectangle, all the numbers in each row and in
each column have to form an arithmetic progression in the order in which they appear.
For example, this is a 3 x 5 arithmetic rectangle:
1 3 5 7 9
2 2 2 2 2
3 1 -1 -3 -5
You are given a grid of integers, some of them substituted by dots. Find out whether it is possible to replace
the dots by some rational numbers in order to obtain an arithmetic rectangle. If there is a solution, find one.
Note: An arithmetic progression is a sequence of numbers such that the difference of any two successive
elements of the sequence is a constant.
The first line of the input contains two positive integers R and C: the dimensions of the grid. R lines follow,
each of them containing C tokens separated by single spaces. Each of the tokens is either a dot (.), or an
integer.
Each number given in the grid is between -100 and 100, inclusive. There are 10 batches of test cases, worth 10
points each. In batches 1 through 9 we have 1 ≤ R, C ≤ 6. The properties of the individual batches are given
below.
If there is no solution, output a single line with the string "No solution."(quotes for clarity). If there are multiple
solutions, pick and output any single solution.
When outputting a solution, output R rows, each with C space-separated rational numbers.
Each rational number shall be printed as "N/D", where D is positive and N and D are relatively prime. If D is 1, omit
the "/D" part.
No number in your output may have more than 20 digits. (It should be easy to satisfy this restriction, its only
intent is to simplify checking your outputs.)
3 5 . . 3 . 5 . . . 5 . . . . . 7 1 6 4 . . 0 . . 3 3 1 . . . 2 . . . 3
1 2 3 4 5 2 3 4 5 6 3 4 5 6 7 4 8/3 4/3 0 -4/3 -8/3 No solution. 1 2 3 1 2 3 1 2 3
Migrated from old NTUJ.
CEOI 2010, Day 1
| No. | Testdata Range | Score |
|---|