## DMOPC '23 Contest 1 P2 - Knights on Chessboard

View as PDF

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 by chessboard. To complete this puzzle, you must place at most knights such that every square on the chessboard contains a knight or is being attacked by a knight. Formally, a knight on square attacks a square if and , or and . Can you solve A. Robbie's ultimate challenge?

#### Input Specification

The first and only line contains the integer .

#### Output Specification

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

#### Sample Input

8

#### 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 knights on the board, although all squares are either covered by a knight or attacked by a knight.