0 人解决，1 人已尝试。
0 份提交通过，共有 1 份提交。
9.9 EMB 奖励。
2208. Recursive ant
单点时限: 2.0 sec
内存限制: 256 MB
Consider a chessboard of size 2^n x 2^n. 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 2^k x 2^k the ant splits it into four parts (quarters) of size 2^(k-1) x 2^(k-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 2^3 x 2^3. 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.
Write a program that:
-
reads positive integers n and m; n describes the size of the board 2^n x 2^n, 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.
Note: each of the four squares in the corners of the board belongs to two peripheries.
输入格式
In the first line 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 2^n-1. The top-left square has coordinates (0,0).
输出格式
In each of four consecutive lines 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.
样例
Input
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 7
Output
0 4 NIE NIE 4 0
题目标签