DMOPC '22 Contest 5 P6 - Threes and Twos

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

Alice is playing a game of Twos and Threes. Twos and Threes is a one-player game played on a two-dimensional N \times M board containing a region to be covered. Alice has an infinite collection of dominoes and triominoes, i.e. tiles of the following shapes:

Alice can place her tiles on the board in any location and orientation. She wins the game if she finds a tiling of the region on the board such that all squares in the region are covered, all squares not in the region are not covered, and no two tiles overlap.

Bob, the inventor of Twos and Threes and archnemesis of Alice, is playing a game of Threes and Twos. The objective of Threes and Twos is to design frustrating regions for Alice. To understand the types of regions that are frustrating for Alice, we will need some definitions. In particular, we say that a region is connected if it is possible to reach any square in the region from any other square in the region travelling orthogonally. Furthermore, we say that a region is frustrating if:

  1. It contains at least two squares.
  2. It is connected.
  3. After removing any single square from the region, it splits into at most two connected regions.
  4. Alice does not have a winning tiling of the region.

Bob wins the game if he finds a frustrating region. Your task is to help Bob win by finding such a frustrating region.

Input Specification

There is no input for this problem.

Output Specification

On the first line output two space-separated integers N and M (1 \le N, M \le 100), the dimensions of the board.

On each of the next N lines, output M characters which are either # or ., representing squares that are in the region and squares that are not in the region, respectively. This should represent a board which contains a frustrating region.


If your output is improperly formatted or it does not contain a frustrating region, you will receive 0 points.

Otherwise, let A be the area of the frustrating region in your solution, and let A' be the area of the frustrating region in the smallest solution.

If A = A', you will receive full points. Otherwise, you will receive a positive number of points based on how close A is to A'. It is guaranteed that a solution with a larger A will not score more points than a solution with a smaller A.

Sample Output

3 5

Explanation for Sample

This output is only provided to clarify the output format. It represents the following region:

Note that it is not a frustrating region because it does not satisfy the fourth property; the following is a winning tiling of the region:


There are no comments at the moment.