Welcome to ZOJ
Select Problem
ZOJ Problem Set - 2670
Nonoptimal Assignments

Time Limit: 5 Seconds      Memory Limit: 32768 KB      Special Judge

You might have heard about assignment problem, stated as follows. Given n×n matrix of integer numbers, one has to choose n elements of the matrix, so that for each row and each column exactly one element is selected from it, and the sum of the selected elements is minimal possible.

Little Mini has just heard about the problem and thinks that it can be solved using so called “greedy algorithm”. That is, she thinks that it is possible to take the smallest element from the first row, after that take minimal element from the second row, that does not belong to the column that was already used, and so on. Each time if there are several possible elements, the one from the smallest column is used.

Her brother Maxi understands that it is not true. To prove it, he wants to construct a matrix where Mini's assignment would be non-optimal. Help him to do so.


Input file contains several test cases. Each case is one line of n (2 <= n <= 100). There is no empty lines between cases.


Output n × n matrix of integer numbers where Mini's algorithm would not find the optimal assignment. If no such matrix exists, output “Impossible” instead. Matrix must contain only non-negative integer numbers not exceeding 100.
After each case, there should be an empty line.


2 0 1
1 10

Source: Andrew Stankevich's Contest #8
Submit    Status