|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||128 MB||0||0||0||0.000%|
After the lesson on arithmetic progressions, the teacher gave Peter homework: a sheet of paper with numbers written in some cells of a R × 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 × 5 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 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.
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.)
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.
3 5 . . 3 . 5 . . . 5 . . . . . 7
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.
1 6 4 . . 0 . .
4 8/3 4/3 0 -4/3 -8/3
1 4 1 2 . 2
3 3 1 . . . 2 . . . 3
1 2 3 1 2 3 1 2 3
This is one of many possible solutions for this input.