DMOPC '23 Contest 1 P2 - Knights on Chessboard

Points: 10 (partial)

Time limit: 2.0s

Memory limit: 1G

Author:

Problem types

The genius chess player A. Robbie gives you a puzzle on an empty $N$ ~N~ by $N$ ~N~ chessboard. To complete this puzzle, you must place at most $\lfloor \frac{N^2 + 3N}{5} \rfloor$ ~\lfloor \frac{N^2 + 3N}{5} \rfloor~ knights such that every square on the chessboard contains a knight or is being attacked by a knight. Formally, a knight on square $(x,y)$ ~(x,y)~ attacks a square $(i,j)$ ~(i,j)~ if $|x-i| = 1$ ~|x-i| = 1~ and $|y-j|=2$ ~|y-j|=2~, or $|x-i| = 2$ ~|x-i| = 2~ and $|y-j|=1$ ~|y-j|=1~. Can you solve A. Robbie's ultimate challenge?

Constraints

$8 \le N \le 2 \times 10^3$ ~8 \le N \le 2 \times 10^3~

Subtask 1 [10%]

$N = 8$ ~N = 8~

Subtask 2 [90%]

No additional constraints.

Input Specification

The first and only line contains the integer $N$ ~N~.

Output Specification

Output $N$ ~N~ lines where each line contains $N$ ~N~ space-separated binary values, where $0$ ~0~ represents an empty square, and $1$ ~1~ represents a knight. If there are multiple solutions, output any of them. If a solution does not exist, output $-1$ ~-1~.

Sample Input

Sample Output

0 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 0 0 1 1 1
1 1 1 0 0 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 0

Explanation for Sample

This sample is only shown to clarify the format of the output. Note that this output is incorrect, as there are greater than $\lfloor \frac{N^2 + 3N}{5} \rfloor$ ~\lfloor \frac{N^2 + 3N}{5} \rfloor~ knights on the board, although all squares are either covered by a knight or attacked by a knight.

Comments

3

rnpmat08_v2 commented on Dec. 15, 2023, 4:07 p.m.

is the limit rounded up or down?

5

BalintR commented on Dec. 16, 2023, 2:42 a.m.

It is rounded down. $\lfloor x \rfloor$ ~\lfloor x \rfloor~ denotes the floor function, the greatest integer not more than $x$ ~x~.