問題一覧 > 通常問題

No.223 1マス指定の魔方陣

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 35
作問者 : tailstails
6 ProblemId : 558 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:49:09

問題文

$N$ 行 $N$ 列の魔方陣を1つ作ってください。
但し、 $Y$ 行目 $X$ 列目の数は $Z$ にしてください。

この問題において、 $N$ 行 $N$ 列の魔方陣とは、
$1$ から $N^2$ までの整数1つずつを $N$ 行 $N$ 列に並べたものであって、
各行、各列、及び2つの対角線それぞれについて、そこに並べた数の総和がいずれも等しくなるもののことをいいます。

$4$ 行 $4$ 列の魔方陣の例:

1 15 14 4
12 6 7 9
8 10 11 5
13 3 2 16

競技プログラミングではあまり出てこないアルゴリズムのため、ヒントとしてWikipedia『魔方陣』の「魔方陣の作り方」を参照してもよい。
答えを求めるためにはいくつかのアルゴリズムを組み合わせる必要がある。

入力

$N$ $X$ $Y$ $Z$

$N \in \{4,8,16\}$
$1 \le X \le N$
$1 \le Y \le N$
$1 \le Z \le N^2$
$X,Y,Z$ はいずれも整数です。

条件を満たす魔方陣が1つ以上存在することが保証されています。

出力

$A_{1,1}$ $A_{1,2}$ $\dots$ $A_{1,N}$
$A_{2,1}$ $A_{2,2}$ $\dots$ $A_{2,N}$
$\vdots$
$A_{N,1}$ $A_{N,2}$ $\dots$ $A_{N,N}$

$N$ 行 $N$ 列の魔方陣を1つ出力してください。但し、 $Y$ 行目 $X$ 列目の数は $Z$ にしてください( $A_{Y,X} = Z$ )。
条件を満たす魔方陣が複数存在する場合には、そのうちのいずれを出力しても構いません。
出力の $y$ 行目に、魔方陣の $y$ 行目の数を、 $1$ 列目の数 $A_{y,1}$ から順に空白区切りで出力してください。
(数の前後に余分な空白があっても構いません。)

サンプル

サンプル1
入力
4 1 2 10
出力
3 13 16 2
10 8 5 11
6 12 9 7
15 1 4 14

$4$ 行 $4$ 列の魔方陣であって、 $2$ 行目 $1$ 列目の数が $10$ であるものを1つ作ります。
条件を満たす魔方陣は上記の他にもありますが、どれを出力しても構いません。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。