No.839 Keep Distance and Nobody Explodes
タグ : / 解いたユーザー数 64
作問者 :
やむなく
/ テスター :
heno239
フレーバーテキスト
信頼できる仲間との通信によって、あなたは爆弾解体に成功した！
残る仕事は解体した部品の運搬である。
危険から逃れ、すっかり安堵して準備を進めていたあなただったが、重大な問題が発覚した！
番号が隣り合う部品を不用意に近づけると、部品が再起動してしまうのだ！
爆弾ケースに部品を入れなおして運ぶ予定だったのだが、位置を工夫しなければ再び爆発の危機にさらされてしまう…
問題文
$N$ を正の
偶数
とし，$N \times N$ のグリッドを考えます．グリッドの各マスに $1$ 以上 $N^2$ 以下の整数のうち $1$ つを書き込み，どの $2$ マスにも同じ数が書かれていないようにします．
グリッドの上から $i$ 番目，左から $j$ 番目のマスを $(i,j)$ と表すことにし，整数 $k\ (1 \le k \le N^2)$ が書かれたマスを $(X_k,Y_k)$ とします．
あなたの目標は，書き込まれた数の差が $1$ であるような $2$ マスの距離の最小値の最大化，すなわち，${\rm min}_{2 \le k \le N^2}\{(X_k-X_{k-1})^2+(Y_k-Y_{k-1})^2\}$ の最大化です．
これを達成する書き込み方を $1$ つ求めてください．
入力
$N$
- $2 \le N \le 300$
- $N$ は正の
偶数
である．
出力
問題文に沿うような書き込み方を $1$ つ出力してください．
具体的には，以下のように $N$ 行出力してください.
マス $(i,j)$ に書かれた整数を $A_{i,j}$ と表します．
$i$ 行目 $(1 \le i \le N)$ には， $N$ 個の整数 $A_{i,j}$ $(1 \le j \le N)$ を空白区切りで出力してください．
$
\begin{matrix}
A_{1,1} & A_{1,2} & \cdots & A_{1,N} \\
A_{2,1} & A_{2,2} & \cdots & A_{2,N} \\
\vdots & \vdots & & \vdots \\
A_{N,1} & A_{2,N} & \cdots & A_{N,N}
\end{matrix}
$
サンプル
サンプル1
入力
2
出力
1 2
3 4
この出力では，
$(X_2-X_1)^2+(Y_2-Y_1)^2=1+0=1$
$(X_3-X_2)^2+(Y_3-Y_2)^2=1+1=2$
$(X_4-X_3)^2+(Y_4-Y_3)^2=1+0=1$
となります．
$N=2$ のとき，${\rm min}_{2 \le k \le N^2}\{(X_k-X_{k-1})^2+(Y_k-Y_{k-1})^2\}$ の値は必ず $1$ となるので，どの書き込み方を出力しても正答となります．
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。