II Olympiad in Informatics 1994/1995
|
Task: SZA
|
Author: Wojciech Rytter
|
II stage contest |
We are given a board of n × n squares, where n is an odd integer meeting the inequality 3 <= n < 50, and a set of k = (n2 - 3) / 2 stones. Each stone has the shape of a rectangle covering exactly 2 squares of the board. The board squares are numbered consecutively by rows - the squares in the first row (from left to right) are numbered from 1 to n, the squares in the second row from n + 1 to 2n, and so on until we reach the bottom right corner square whose number is n2.
We cut any three squares out of the board, and next we want to cover it with the stones. We require that every square not removed should be covered with exactly one stone (covering also one adjacent square) and that cut out squares remain uncovered.
Is it always possible?
If there are many ways to cover the board with stones, your program should write only one (arbitrary) of them.
The data in the file SZA.IN are written correctly, and your program need not verify that.
7 17 25 40a correct file SZA.OUT may contain:
18 19 20 21 8 9 10 11 12 13 14 7 6 5 4 3 1 2 15 22 16 23 29 36 30 37 24 31 32 39 43 44 38 45 46 47 48 49 41 42 33 34 35 28 26 27
For the file SZA.IN:
7 25 32 40the file SZA.OUT should contain only one word:
NIE
Your program should look for the file SZA.IN in the current directory and create the file SZA.OUT also in the current directory. The source file containing the program written by you should be named SZA.???, where ??? are substituted by at most three-letter abbreviation of the programming language used. The same program in an executable form should be written in a file SZA.EXE.