No.3728 Half and Half, and Double
Story
There is a cake shaped like a square grid. Yukari and Akari are going to split this cake into two equal parts, then each spread additional cream on the sides of their own part and eat it.
They agreed that each of them would use $1$ pack of cream for the sides, but Akari has started wanting to secretly use $2$ packs.
However, with an ordinary bisection, the difference in the density of the spread cream would reveal that the amounts of cream differ. Please show them a way to cut the cake that splits it into two equal parts while making the side areas have a ratio of $1:2$.
Problem Statement
Output one example of a way to divide a $2N \times 2N$ square grid along its cells into $2$ connected shapes $A$ and $B$ that satisfies all of the following conditions. If no such division is possible, output -1.
- $A$ and $B$ contain the same number of cells
- The perimeter of $A$ is exactly $2$ times the perimeter of $B$
Here, a shape is connected if, for any $2$ cells belonging to the shape, one can move from one to the other by moving up, down, left, or right through only cells belonging to the shape.
The perimeter of a shape is the number of edges of cells belonging to the shape that are adjacent to a cell not belonging to the shape (including the outside of the grid).
$A$ or $B$ may be a hollow shape, in which case its perimeter is the sum of the lengths of the inner and outer perimeters.
Constraints
- All input values are integers
- $1 \leq N \leq 500$
Input
The input is given from standard input in the following format.
$N$
Output
If a division satisfying the conditions exists, output one example of it in the following format. Here, $S_i$ is a string of length $2N$, and the $j$-th character of $S_i$ is A if the cell in the $i$-th row from the top and the $j$-th column from the left belongs to $A$, and B if it belongs to $B$.
If no division satisfying the conditions exists, output -1.
$S_1$
$S_2$
$\vdots$
$S_{2N}$
Note that $A$ or $B$ may be a hollow shape, but each must be connected.
Print a newline at the end.
Visualizer
A web-based visualizer for the output is available here.
During the contest, sharing visualization results and mentioning solutions or analysis 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
Sample 1
Input
5
Output
BBAAAAAAAA BBBBBBBAAA ABBBBBBBAA ABBBBBBBAA ABBBBBBBAA ABBBBBBBAA ABBBBBBBAA AABBBBBBAA AAAAAAAAAA AAAAAAAAAA
An example of the division is shown in the figure below.
Shapes $A$ and $B$ each contain $50$ cells, which is equal, and the perimeter of $A$ is $64$ and the perimeter of $B$ is $32$.
Sample 2
Input
1
Output
-1
No matter how the $2 \times 2$ grid is divided, the conditions are not satisfied.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。