No.3741 Used to be Polyominal Constructive
Story
kencho came up with the following problem.
"You are given $3$ polyominoes, each fitting in an $N \times N$ grid. Output one way to translate each polyomino so that every $2$ of the polyominoes do not overlap and are adjacent by sharing an edge."
This problem looked interesting at first glance, but it turned out that speeding up a nearly brute-force solution with SIMD made it faster than the intended solution (if you have time, try to think of an $O(N^2 \log N)$ solution).
So kencho changed the format of the problem and decided to have you create a test case that defeats "incorrect solutions that randomly make polyominoes adjacent to each other and search for a consistent combination".
Incidentally, although the word polyominal has a few uses in papers and elsewhere, it is hardly ever used, and it seems that using polyomino as is to modify a noun is the common practice.
Problem Statement
Consider an $N \times N$ grid where each cell contains # or .. Regarding the cells of a grid $G$ that contain # as unit squares, we call the set of those squares the figure represented by $G$.
A figure is called a polyomino if it is non-empty and it is possible to move from any unit square to any other unit square by following unit squares that share an edge.
Find an integer $N$ and $3$ grids $(G_1, G_2, G_3)$ of size $N \times N$ satisfying all of the following conditions. Let $P_i$ be the figure represented by $G_i$.
- $N$ is an integer between $1$ and $666$, inclusive.
- For $i = 1, 2, 3$, $P_i$ is a polyomino.
- The number of ways to make $P_1$ and $P_2$ adjacent by translation is at least $10^5$.
- The number of ways to make $P_2$ and $P_3$ adjacent by translation is at least $10^5$.
- The number of ways to make $P_3$ and $P_1$ adjacent by translation is at least $10^5$.
- The number of ways to simultaneously make $P_1$ and $P_2$, $P_2$ and $P_3$, and $P_3$ and $P_1$ adjacent by translation is at least $1$ and at most $10$.
What the number of ways to make them adjacent means
In this problem, we consider translating polyominoes by integer vectors, without rotating or reflecting them.
Translation takes place on an infinitely extending square lattice, and the figure after translation does not need to fit within the original $N \times N$ grid.
Two polyominoes are said to be adjacent if both of the following conditions hold.
- The unit squares of the 2 polyominoes do not overlap.
- There exist a unit square of one polyomino and a unit square of the other polyomino that share an edge (merely sharing a vertex does not count as adjacent).
The number of ways to make $P_i$ and $P_j$ adjacent is the number of translation vectors such that, when the position of $P_i$ is fixed and $P_j$ is translated by an integer vector, the 2 polyominoes are adjacent. Even if they share multiple edges, the same translation vector counts as $1$ way.
The number of ways to simultaneously make $P_1$ and $P_2$, $P_2$ and $P_3$, and $P_3$ and $P_1$ adjacent is the number of ordered pairs $(v_2, v_3)$ such that, when the position of $P_1$ is fixed and $P_2, P_3$ are translated by integer vectors $v_2, v_3$ respectively, all 3 pairs are adjacent.
Therefore, an arrangement obtained merely by translating all the polyominoes by the same amount is not counted as a different way.
Input
This problem is output-only. No input is given.
Output
Output the integer $N$ and the grids $G_1, G_2, G_3$ in the following format.
$N$
$G_{1, 1, 1} G_{1, 1, 2} \ldots G_{1, 1, N}$
$G_{1, 2, 1} G_{1, 2, 2} \ldots G_{1, 2, N}$
$\vdots$
$G_{1, N, 1} G_{1, N, 2} \ldots G_{1, N, N}$
$G_{2, 1, 1} G_{2, 1, 2} \ldots G_{2, 1, N}$
$G_{2, 2, 1} G_{2, 2, 2} \ldots G_{2, 2, N}$
$\vdots$
$G_{2, N, 1} G_{2, N, 2} \ldots G_{2, N, N}$
$G_{3, 1, 1} G_{3, 1, 2} \ldots G_{3, 1, N}$
$G_{3, 2, 1} G_{3, 2, 2} \ldots G_{3, 2, N}$
$\vdots$
$G_{3, N, 1} G_{3, N, 2} \ldots G_{3, N, N}$
$G_{i,j,k}$ denotes the character written in the cell at the $j$-th row from the top and the $k$-th column from the left of grid $G_i$.
Print a newline at the end.
Visualizer
A web version of the visualizer for output results is available here.
During the contest, sharing visualization results and mentioning solutions or considerations are prohibited. Please be careful.
In principle, we do not accept questions about the specifications of the visualizer. Please use it only as an auxiliary tool.
Sample
Output
2 #. ## .# .# ## ##
Note that this sample output only illustrates the output format, and it will be judged as WA if submitted.
For $P_1, P_2, P_3$ represented by this output, the respective numbers of ways are as follows.
-
The number of ways to make $P_1$ and $P_2$ adjacent by translation is $9$.
-
The number of ways to make $P_2$ and $P_3$ adjacent by translation is $10$.
-
The number of ways to make $P_3$ and $P_1$ adjacent by translation is $11$.
-
The number of ways to simultaneously make $P_1$ and $P_2$, $P_2$ and $P_3$, and $P_3$ and $P_1$ adjacent by translation is $17$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。