Submit | All submissions | Best solutions | Back to list |
Problem hidden on 2012-05-14 10:50:42 by :D
MAGICSQU - Magic Square! |
Given an nxn matrix, if it satisfy the next constraints it could be called a "Magic Square".
Constraints:
* The sum of the n rows, n columns and the two main diagonals of the matrix must be equal to the same number m, called magic constant
* the n2 positions of the matrix must contains natural numbers between 1 to n2, with no repetitions.
Input
Each test case consist in a natural number n (0 < n <= 20) denoting the matrix dimension. Then, the next n2 natural numbers will represent the values that initially contains the matrix.
For each position aij (1 <= i,j <= n) of the matrix, we have: 0 <= aij <= n2, for all ij.
A value of 0 in an initial position aij of the matrix means that you must find a number to complete that place. A non-zero value means that you cannot change that value for the given position.
Output
For each case you must print the case number (starting from 1).
Then, in the next n lines you must print the magic square if exists or the phrase ''No Solution'' (without the quotes) if doesn't exist a solution for the given initial configuration.
See the output example.
If for a given initial configuration exists more than one solution, you should give the lower one assuming a lexicographic order. For lexicographic comparison you should consider lines in first place.
Print a blank line between test cases.
For example:
2 7 6
9 5 1
4 3 8
it's lexicographically before than:
4 3 8
9 5 1
2 7 6
Example
Input:3
8 0 0
0 0 0
0 0 0
2
1 1
0 0
Output:
Case #1
8 1 6
3 5 7
4 9 2
Case #2
No Solution
Added by: | Coach UTN FRSF |
Date: | 2011-06-17 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |
hide comments
|
|||||
2011-06-18 16:21:06 Chetan Gupta
for input: 3 4 0 0 0 0 0 0 0 0 what should be the output?? a) 4 3 8 9 5 1 2 7 6 or b) 4 9 2 3 5 7 8 1 6 |
|||||
2011-06-18 16:21:06 Coach UTN FRSF
@blashyrkh Your solution is quite good but, like you said, some of your answers are not lexicographically sorted |
|||||
2011-06-18 16:21:06 blashyrkh
@Coach UTN FRSF: What's wrong with my program #5258894? Some of my answers are not lexicographically lowest or there is something more seriuos? |
|||||
2011-06-18 16:21:06 Coach UTN FRSF
@Krzysztof Lewko: Why is that weird? there are numbers that are less than 2!!! @[Trichromatic] XilinX There's no upper bound. Not all test cases have an initial configuration completly empty :) |
|||||
2011-06-18 16:21:06 Coach UTN FRSF
@blashyrkh thanks, it was fixed! Yes, input finish with EOF Last edit: 2011-06-17 12:20:08 |
|||||
2011-06-18 16:21:06 blashyrkh
"No Solution" or "no solution"? Is blank line after the last test case's output needed? Input ends at EOF? Last edit: 2011-06-17 10:54:26 |
|||||
2011-06-18 16:21:06 :D
It could be that there are more test sets and your program fails on the first with N<=2 (just guessing). |
|||||
2011-06-18 16:21:06 Krzysztof Lewko
Weird, for assert(n<=2) it gives WA... |
|||||
2011-06-18 16:21:06 [Rampage] Blue.Mary
What's the upper bound of n? |