No.1974 2x2 Flipper
Problem Statement
There is a grid with $H$ rows and $W$ columns, whose cells are painted black or white. Initially, all cells are painted white. The cell in the $i$-th row and $j$-th column is denoted by $(i,j)$.
Find the maximum number of cells painted black that can be obtained by performing the following operation a finite number of times, along with a specific grid state that achieves it.
Operation
Choose $i,j$ satisfying $1 \leq i \leq H-1, 1 \leq j \leq W-1$.
For each of $(i,j),\ (i+1,j),\ (i,j+1),\ (i+1,j+1)$, repaint it black if it is painted white, and white if it is painted black.
Constraints
- $\displaystyle 1 \leq H,W \leq 1000$
- All input values are integers.
Input
The input is given from standard input in the following format.
$H\ \ W$
Output
Output the answer in the following format, followed by a newline at the end.
If there are multiple possible answers, you may output any of them.
$ans$ denotes the maximum number of cells painted black.
$A_{i,j}$ denotes the element in the $i$-th row and $j$-th column of the grid you found; $0$ means white and $1$ means black.
$ans$
$A_{1,1}\ \ A_{1,2} \ \dots \ A_{1,W}$
$A_{2,1}\ \ A_{2,2} \ \dots \ A_{2,W}$
$:$
$A_{H,1}\ \ A_{H,2} \ \dots \ A_{H,W}$
Sample
Sample 1
Input
2 3
Output
4 1 1 0 1 1 0
By performing $1$ operation with $i=1,j=1$, the grid becomes the state shown in the output above.
It can be shown that the number of cells painted black cannot be made $5$ or more with a finite number of operations, so the maximum is $4$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
magsta