신각자 선발 시험에서 우수한 성과를 이루어낸 마슈 반데드는, 마지막으로 신각자의 자격을 증명하기 위한 단 하나의 시련만을 남겨두고 있다! 마슈가 받은 마지막 시련의 내용은, 다음과 같다.
더도 말고 덜도 말고 $K$만 같아라
마법계의 관용어와 속담에 대해서 잘 모르는 당신을 위해 시련을 알기 쉽게 번역하면, 다음과 같다:
물론 마슈 또한 시련을 이해하지 못한 것은 마찬가지이므로 시련의 감독관이 한눈을 파는 사이 매우 빠르게 당신에게 도움을 청할 것이다! 마슈를 위해 위의 시련에 맞는 마법사의 격자판을 만들 수 있는지 알려주고, 만들 수 있다면 격자판을 어떻게 만들어야 하는지 알려주어라.
첫 번째 줄에 양의 정수 $N$과 $K$가 공백으로 구분되어 주어진다. $\left(1 \leq N \leq 1\,000;1 \leq K \leq 10^9\right)$
만약 $K$개의 동전을 전부 사용해 마법사의 격자판을 만들 수 없다면 −1을 출력한다.
그렇지 않다면 다음 $N$개의 줄에 $N$개의 정수를 공백으로 구분하여 출력한다. $i$번째 줄의 $j$번째 수는 격자판의 $i$행 $j$열 칸에 배치한 동전의 수를 의미한다.
3 7
1 2 1
0 1 0
1 0 1
$3\times 3$ 격자판에 총 $1+2+1+0+1+0+1+0+1=7$개의 동전을 올렸고, 모든 인접한 칸은 동전의 개수가 $1$ 차이 나므로, 이 격자판은 마법사의 격자판이다.
3 1
-1
어떤 방법을 사용해도 동전이 $1$개 올려진 $3\times 3$ 격자판이 존재하지 않음을 증명할 수 있다.
굉장히 재미있는 형태의 문제로, 많은 양의 사고를 필요로 하지만 그에 비례한 만큼 재미있었다. 심지어 대회 현장이었는데도!
사실 대회 현장에서는 문제를 어렵게 읽을 필요가 없기에 가장 쉬운 방법을 선택했다. 바로 최대한 맵의 전체에 코인을 준일하게 배치하는 방법으로, 예제 입력 1을 보고 빠르게 힌트를 얻어 채택했다. 전체적인 알고리즘은 다음과 같다.