In the event of technical difficulties with Szkopuł, please contact us via email at szkopul@fri.edu.pl.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (irc.pirc.pl
) in #szkopul
channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
After the lesson on arithmetic
progressions, the teacher gave Peter homework: a sheet of paper with numbers
written in some cells of a 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 arithmetic rectangle:
1 | 3 | 5 | 7 | 9 |
2 | 2 | 2 | 2 | 2 |
3 | 1 | -1 | -3 | -5 |
Peter is lazy to do such tasks manually. He wants you to write a program that will do it for him.
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 one integer
(
): the number of test cases.
The following lines contain the descriptions of the test cases.
The first line of a test case description contains two positive integers and
: the dimensions of the grid.
lines follow, each of them containing
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 .
The properties of the individual batches are given below.
Batch 1. All numbers are already filled in.
Batch 2. Either or
in each test case.
Batch 3. in each test case.
Batch 4. Each test case has a unique solution that can be found using the approach suggested in the first example.
Batch 5. Each test case has a unique solution, and the solution contains integers only.
Batch 6. Each test case has a unique solution.
Batch 7. Each test case either has a unique solution that contains integers only, or has no solution at all.
Batch 8. Each test case either has a unique solution, or has no solution at all.
Batch 9. Arbitrary test cases.
Batch 10. Arbitrary test cases with .
Your program should output the results to the respective test cases in the following format.
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 for a test case, output rows, each with
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.)
For the input data:
1 3 5 . . 3 . 5 . . . 5 . . . . . 7
the correct result is:
1 2 3 4 5 2 3 4 5 6 3 4 5 6 7
The above example can be solved as follows: First, note that the second number in the last column must be 6. Then fill in row 1, row 2, and finally fill in columns 1 through 4.
For the input data:
1 1 6 4 . . 0 . .
the correct result is:
4 8/3 4/3 0 -4/3 -8/3
For the input data:
1 1 4 1 2 . 2
the correct result is:
No solution.
For the input data:
1 3 3 1 . . . 2 . . . 3
the correct result is:
1 0 -1 3 2 1 5 4 3
This is one of many possible solutions for this input.
Task author: Michal Forisek.