IOI '14 - Taipei, Taiwan


Place tiles on the floor

We have a 2n by 2n floor with 4n unit squares. Each square can be identified by its x and y coordinates (both from 0 to 2n − 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 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.


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).


Write a program to cover the floor with tiles.

Input Format

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

Output Format

The output should consist of a list of tile positions. Each line of the output should contain six space-separated integers x1, y1, x2, y2, x3, and y3 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

Subtask 1 [5% of points]

  • n is 1.

Subtask 2 [15% of points]

  • 1 ≤ n ≤ 2.

Subtask 3 [20% of points]

  • 1 ≤ n ≤ 8, and x = y = 0.

Subtask 4 [60% of points]

  • 1 ≤ n ≤ 8.

All Submissions
Best Solutions

Point Value: 15 (partial)
Time Limit: 2.00s
Memory Limit: 64M
Added: Jun 25, 2014

Languages Allowed:

Comments (Search)

This problem got added pretty recently - is a working verifier uploaded for this problem? I've hand-tested some small cases and don't appear to have any bugs on the small cases, so I'd expect to solve at least a couple cases in subtasks 1 and 2.

Sorry about that. It's fixed now.