| History of OI -> IV OI 1996/1997 -> Problems |  |
|
IV Olimpiada Informatyczna 1996/1997
|
|
Task: REK
|
Author: Wojciech Rytter
|
| II stage contest |
| Source file | REK.??? (e.g. PAS,C, CPP) |
| Executable file | REK.EXE |
| Input file | REK.IN |
| Output file | REK.OUT |
Consider a chessboard of size 2n x 2n. Some of its squares are marked and called forbidden squares. An ant is going to visit all squares of the chessboard except the forbidden ones. Each of the squares has to be visited exactly once. The tour begins in the start square, which is the top-left square of the board and has to finish in one of the periphery squares (the ant want to leave the board in the end). We assume that the start square is not forbidden. In a single step the ant can move to one of at most four neighbouring squares (i.e. she can move up, down, left or right).
The walk of our ant is recursive in a sense: to round the square of size 2k x 2k the ant splits it into four parts (quarters) of size 2k-1 x 2k-1 and then rounds each of them. It means if the ant enters one of the quarters she cannot leave it before visiting all the squares in this quarter that are not forbidden.
In the Figure 1 you can see two routes of a recursive tour of the ant on the board of size 23 x 23. Both routes begin in the start square (0,0). First of them is finished in the top periphery and the second in the left periphery of the board.
Figure 1
Task
Write a program that:- reads positive integers n and m from the text file REK.IN; n describes the size of the board 2n x 2n, m is the number of forbidden squares; then reads coordinates of all forbidden squares,
- for each of the four peripheries of the board finds a square at which a recursive tour described before can be finished or states that such a square does not exist,
- writes the result to the text file REK.OUT.
Input
In the first line of the text file REK.IN there is one positive integer n <= 30.In the second line there is the number of forbidden squares m, m <= 50.
In each of the following m lines there is a pair of non-negative integers i, j separated by a single space; i and j are coordinates of a forbidden square (i is the number of line and j is the number of column). The lines and columns of the board are numbered from 0 to 2n-1. The top-left square has coordinates (0,0).
Output
In each of four consecutive lines of the text file REK.OUT there should be written two non-negative integers separated by a single space. These integers should be coordinates (the number of line and column) of the end square of an appropriate tour. If such a square does not exists the word NIE (which means NO in Polish) should be written. In the first line there should be the square of the tour ending on the top periphery, in the second - on the right periphery, in the third - on the bottom periphery and in the fourth line - on the left periphery.
Example
For the file REK.IN (describing the board shown in the figure):3 15 2 0 1 0 3 0 6 0 7 0 6 1 7 1 6 2 7 2 6 3 7 3 0 2 0 3 0 6 0 7 1 6 1 7the correct result is the file REK.OUT
0 4 NIE NIE 4 0
Print friendly version