Problem M
OK Maps
Jayce is creating a contraption that will help link Piltover’s hexgates together. To help him, he needs to create something known as an OK map. An OK map is a $N \times N$ grid of squares, where each square in the grid contains either $0$ or $1$.
In addition, define the following:
-
A prime rectangle is a rectangle within the grid that only covers $1$’s that can no longer be expanded. Thus, if we expanded a prime rectangle upward, downwards, leftwards, or rightwards, the rectangle would either go out of bounds of the grid or no longer contain only $1$’s. Denote the number of prime rectangles within the OK Map by $P$.
-
An essential prime rectangle is a prime rectangle that covers at least one $1$ that cannot be covered by any other prime rectangle. Denote the number of essential prime rectangles within the OK Map by $E$.
Given an integer $N$ and $M$, please help Jayce to create an $N \times N$ OK map such that $P - E = M$. If there are multiple such OK maps, any one is acceptable. Note the count of prime rectangles will include all essential prime rectangles.
Input
The only line of input contains two space-separated integers $N \: (3 \leq N \leq 300)$ and $M \: ( 0 \leq M \leq 2N - 4)$, where $N$ repesents the size of the grid you must create, and $M$ represents the necessary difference between the number of prime rectangles $P$ and essential prime rectangles $E$ in your OK map.
Output
Output a $N \times N$ table, filled with $0$’s and $1$’s, such that $P - E = M$. There should be no spaces between cells in the same row, and rows should be separated by new lines.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 1 |
0100 0100 1100 1000 |
