ZOJ Problem Set - 2670
You might have heard about
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.
InputInput file contains several test cases. Each case is one line of n (2 <= n <= 100). There is no empty lines between cases.
OutputOutput 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.
Source: Andrew Stankevich's Contest #8