Given a chessboard of $n$ by $n$, is it possible to place m pieces in it so that no more than $k$ pieces appear in each row, each column, and each 45 degree line? Note that there are two 45 degree lines for a cell $(x, y)$ not in the corners. That is, the first one goes through … $(x-1, y + 1)$, $(x, y)$, $(x + 1, y -1)$, … and the second one goes through $(x + 1, y + 1)$, $(x, y)$, $(x - 1, y - 1)$, …
Subtasks
5pt. $n = 3$, $m = 4$, and $k = 2$.
5pt. $n = 3$, $m = 3$, and $k = 1$.
15pt. $n = 6$, $m = 6$, and $k = 1$.
20pt. $n$ is no more than 8, $m$ is no more than 16, and $k$ is no more than 1.
50pt. $n$ is no more than 12, $m$ is no more than 30, and $k$ is no more than 10.
5pt. $n$ is no more than 15, $m$ is no more than 100, and $k$ is no more than 100.
Hints
You simply try to place the pieces into each cell in a row by row manner. Each time you place a piece, you need to check if your placement is valid.
There are various optimizations you can use. For example, if you have placed m pieces in the same row then you should go on to the next row.
To get the last 5 points you need a very careful implementation that tracks the number of pieces that are already placed in each row, column a 45 degree line.
Input Format
n1 m1 k1
n2 m2 k2
...(until EOF)
For each line, you have to find out whether it is possible or not to place m pieces in a chessboard of $n$ by $n$ so that no more than $k$ pieces appear in each row, each column, and each 45 degree line.
Output Format
If it is possible to place $m$ pieces in the chessboard, print one possible solution.
If it is not possible to place m pieces in the chessboard, print N.
Problem Description
Given a chessboard of $n$ by $n$, is it possible to place m pieces in it so that no more than $k$ pieces appear in each row, each column, and each 45 degree line? Note that there are two 45 degree lines for a cell $(x, y)$ not in the corners. That is, the first one goes through … $(x-1, y + 1)$, $(x, y)$, $(x + 1, y -1)$, … and the second one goes through $(x + 1, y + 1)$, $(x, y)$, $(x - 1, y - 1)$, …
Subtasks
Hints
Input Format
For each line, you have to find out whether it is possible or not to place m pieces in a chessboard of $n$ by $n$ so that no more than $k$ pieces appear in each row, each column, and each 45 degree line.
Output Format
If it is possible to place $m$ pieces in the chessboard, print one possible solution.
If it is not possible to place m pieces in the chessboard, print
N.Sample Input
Sample Output