DominoTilings | Topcoder Archive

Problem Statement

You are given a long n. Your task is as follows:

Choose any R times C rectangle such that R is at most 13 and R*C is at most 14,400.
Within that rectangle, draw a 4-connected shape that has exactly n different domino tilings.
Return your shape formatted as a String[] with R elements, each containing C characters. Use '.' for cells that belong to your figure and '#' for cells that don't. (Recall that all '.'s must form one 4-connected component.)

You may assume that a solution always exists. If there are multiple solutions, you may return any of them.

Definition

Class:: DominoTilings
Method:: solve
Parameters:: long
Returns:: String[]
Method signature:: String[] solve(long n)
(be sure your method is public)

Notes

A domino is a 2x1 figure that can be used to cover two adjacent cells of the grid (either horizontally or vertically).
A domino tiling is a collection of dominoes that covers each '.' cell exactly once and no other cells.
Two tilings are considered different if two cells are covered by the same domino in one tiling and by two different dominoes in the other tiling.
Two cells that belong to the figure are directly connected if they share a side. A figure is 4-connected if each pair of cells in the figure is connected, either directly or via other cells.

Constraints

n will be between 2 and 1018, inclusive.

Examples

```
2
```
```
Returns: {"##########...##########", "##########.#.##########", "##########...##########" }
```
The returned figure is just a 3x3 square with a hole in the middle. It has two tilings: --| and |-- |#| |#| |-- --|
```
4
```
```
Returns: {"##########...##########", "##########...##########", "##########..###########" }
```
The returned figure is just a 3x3 square with a hole in a corner. It has four tilings: ||| --| |-- --| ||| --| |-- ||| --# --# --# ||#

Returns: {"##########....##########", "##########....##########", "##########....##########", "##########....##########" }

Returns: {"#########.....#########", "#########.....#########", "#########..#..#########", "#########.....#########", "#########.....#########" }

259009513044645817

Returns: {"......................", "......................", "......................", "......................", "......................", "......................", "......................" }

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.