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$ $⌊ \frac{N^{2} + 3 N}{5} ⌋$ 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 \leq N \leq 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

Copy

Sample Output

Copy

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$ $⌊ \frac{N^{2} + 3 N}{5} ⌋$ 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$ $⌊ x ⌋$ denotes the floor function, the greatest integer not more than $x$ $x$ .