No.3337 Divide and Conquer
Problem Statement
You are a minister of a certain kingdom. The kingdom has the shape of an $N \times N$ ($N$ is a multiple of $3$) square grid graph, where each of the $N^2$ vertices corresponds to $1$ city and each of the $2N(N-1)$ edges corresponds to $1$ road.
More precisely, each city is represented by a pair of integers $(i,\ j)$ ($i,\ j$ are integers between $1$ and $N$, inclusive), and the cities directly connected by a road to $(i,\ j)$ are the at most $4$ cities $(i - 1,\ j), (i + 1,\ j), (i,\ j - 1), (i,\ j + 1)$.
There is no way to travel between cities other than using these roads.
One day, the king ordered you to devise a policy to improve public order in the country. This kingdom is inhabited by $3$ races, humans, elves, and dwarves, and conflicts between the races never ceased.
You consider an arrangement of cities that allows $1$ race to unite to be a risk, so you decided to limit the inhabitants of each of the $N^2$ cities to $1$ race, and then to make the number of cities reachable without passing through cities inhabited by other races as small as possible.
Also, to prepare for emergencies, you decided to ensure that whenever any $2$ races cooperate, they do not need to pass through cities inhabited by the remaining $1$ race.
Now, let $M_{min}$ be the minimum integer $M$ for which there exists an assignment of races to cities satisfying all of the following conditions. Find one example of such an assignment under $M = M_{min}$.
- The number of cities assigned to each race is the same.
- From any city $c$, the number of cities that can be reached by passing only through cities assigned the same race as the one assigned to $c$ is at most $M$, including $c$ itself.
- Let $a, b$ be any $2$ cities. If the race $x$ assigned to $a$ and the race $y$ assigned to $b$ are different, it is possible to travel from $a$ to $b$ by passing only through cities assigned $x$ or $y$.
Constraints
- All inputs are integers.
- $3 \leq N \leq 2025$
- $N$ is a multiple of $3$.
Input
The input is given from standard input in the following format.
$N$
Output
Output the answer in the following format.
$S_1$ $S_2$ $\vdots$ $S_N$
$S_i$ is a string of length $N$, and the $j$-th character of $S_i$ must be H if the race assigned to city $(i,\ j)$ is human, E if it is elf, and D if it is dwarf.
Print a newline at the end.
Sample
Sample 1
Input
3
Output
HED HDD EEH
The figure below shows the assignment corresponding to the sample output. Blue vertices represent cities assigned to humans, red vertices represent cities assigned to elves, and green vertices represent cities assigned to dwarves.
This assignment satisfies the conditions of the problem when $M=3$, and no assignment satisfying the conditions of the problem exists when $M \leq 2$, so this is a correct answer.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
cn_449