Problem E
Ex Officio

“I have come to the conclusion that one useless man is called a disgrace, that two are called a law firm, and that three or more become a Congress!” ­–Peter Stone.

The bureaucracy of government is often criticized; the frequency of fruitless meetings, the inefficiency of discussions and the like are common topics of ridicule.

The government is trying to change that impression. To start, they have hired you to redesign the structure of the capitol to decrease inefficiency.

The capitol can be represented as a grid with $R$ rows and $C$ columns. Each of the cells in this grid is a chamber where meetings can be held. Right now, there are no walls between any of the chambers; thus, in one minute, it is possible to travel directly from one chamber to any of the chambers it shares a side with in the grid. That is, if we denote the chamber at the $r^\text {th}$ row and $c^\text {th}$ column of this grid as chamber $(r, c)$, then in one minute one can travel from chamber $(r, c)$ to any of the chambers $(r-1, c)$, $(r, c+1)$, $(r+1, c)$ or $(r, c-1)$ (if they exist).

Meetings are periodically held in different chambers, and unfortunately, many congressmen end up getting lost and fail to find their way to the required chamber, eating up precious time. Hence, the first requirement is

  1. to build walls between chambers in such a way that there is exactly one way to travel between any two chambers.

At the same time, it is imperative that no matter which chamber the meeting is held in, all the congressmen in the capitol (who could be in any of the other chambers) can be gathered in a short amount of time. Hence, define the gathering time of a chamber $(r, c)$ to be the maximum number of minutes required to travel from any chamber to chamber $(r, c)$, assuming one takes the unique direct route. The second requirement is

  1. to minimize the maximum gathering time across all chambers.

That is, across all wall-building plans satisfying the first requirement, you should choose one that minimizes the maximum gathering time.

\includegraphics[width=0.65\textwidth ]{exco.png}
Figure 1: Illustration of Sample Input 1.

Help the government get its act together and eliminate the unnecessary bureaucracy!


The first and only line of input contains two integers, $R$ and $C$ ($1 \leq R, C, R \cdot C \leq 200\, 000$), the number of rows and the number of columns of the grid, respectively.


Output $R+1$ rows, representing a wall-building plan satisfying the requirements in the following format:

  • The first row should contain $2 \cdot C$ characters. The $c^\text {th}$ character in this row should be

    • a space, if $c$ is odd;

    • _, if $c$ is even.

  • The next $R$ rows should each contain $2 \cdot C+1$ characters. The $c^\text {th}$ character in the $r^\text {th}$ of these rows should be

    • |, if $c = 1$ or $c = 2 \cdot C+1$;

    • _, if $c$ is even and $r = R$;

    • a space, if $c$ is even and there is no wall between chambers $(r, c/2)$ and $(r+1, c/2)$;

    • _, if $c$ is even and there is a wall between chambers $(r, c/2)$ and $(r+1, c/2)$;

    • a space, if $c$ is odd and there is no wall between chambers $(r, (c-1)/2)$ and $(r, (c+1)/2)$;

    • |, if $c$ is odd and there is a wall between chambers $(r, (c-1)/2)$ and $(r, (c+1)/2)$.

If there are multiple correct answers, you can output any of them.

Sample Input 1 Sample Output 1
3 5
 _ _ _ _ _
| |_   _| |
|  _   _  |
|_|_ _ _|_|
Sample Input 2 Sample Output 2
2 2
 _ _
| | |
|_ _|

Please log in to submit a solution to this problem

Log in