問題一覧 > 通常問題

No.839 Keep Distance and Nobody Explodes

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 64
作問者 : やむなくやむなく / テスター : heno239heno239
5 ProblemId : 2617 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-06-15 00:17:36

フレーバーテキスト

信頼できる仲間との通信によって、あなたは爆弾解体に成功した!
残る仕事は解体した部品の運搬である。
危険から逃れ、すっかり安堵して準備を進めていたあなただったが、重大な問題が発覚した!
番号が隣り合う部品を不用意に近づけると、部品が再起動してしまうのだ!
爆弾ケースに部品を入れなおして運ぶ予定だったのだが、位置を工夫しなければ再び爆発の危機にさらされてしまう…

問題文

$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もしくは右上の雲マークをクリックしてアカウントを作成してください。