IOI '14 Practice Task 3 - Tile

View as PDF

Submit solution


Points: 10 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type
IOI '14 - Taipei, Taiwan

Place tiles on the floor

We have a 2^n by 2^n floor with 4^n unit squares. Each square can be identified by its x and y coordinates (both from 0 to 2^n-1). We want to cover this floor with four types of 2 by 2 L-shaped tiles, as shown in the following figure. The tiles cannot overlap, and they can only be placed on the grid boundary. In addition, there is exactly a square that we cannot cover with tiles. Please find a way to cover the entire floor with tiles.

Example

In the following example we have n = 3 and 64 squares. The blue square at (1, 6) cannot be covered by any tile. This figure shows a possible way to cover the floor. To identify a tile we will use the x and y coordinates. For example, the green tile in the figure can be identified by (6, 2), (7, 2), and (7, 3).

Statement

Write a program to cover the floor with tiles.

Input Specification

The input consists of one line with 3 integers n, x, and y. n indicates that the size of the floor is 2^n by 2^n. x and y are the coordinates of the square that cannot be covered with tiles.

Output Specification

The output should consist of a list of tile positions. Each line of the output should contain six space-separated integers x_1, y_1, x_2, y_2, x_3, and y_3 to describe the position of one tile. For example, if we want to place the green tile as the first tile, we can output the integers 6, 2, 7, 2, 7, and 3. The three squares of a tile can appear in any order, so we can also set them as 7, 2, 7, 3, 6, and 2. The tiles can also appear in any order.

Sample Input 1

1 0 0

Sample Output 1

0 1 1 0 1 1

Sample Input 2

1 1 0

Sample Output 2

0 0 0 1 1 1

Constraints

Subtask 1 [5%]

n = 1

Subtask 2 [15%]

1 \le n \le 2

Subtask 3 [20%]

1 \le n \le 8

x = y = 0

Subtask 4 [60%]

1 \le n \le 8


Comments

There are no comments at the moment.