結果
| 問題 |
No.223 1マス指定の魔方陣
|
| コンテスト | |
| ユーザー |
 rpy3cpp
|
| 提出日時 | 2015-06-09 17:38:14 |
| 言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
| 結果 |
AC
|
| 実行時間 | 33 ms / 5,000 ms |
| コード長 | 7,131 bytes |
| コンパイル時間 | 77 ms |
| コンパイル使用メモリ | 13,696 KB |
| 実行使用メモリ | 11,776 KB |
| 最終ジャッジ日時 | 2024-07-06 15:13:07 |
| 合計ジャッジ時間 | 3,093 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 46 |
ソースコード
def read_data():
N, X, Y, Z = map(int, input().split())
return N, X, Y, Z
def solve(N, X, Y, Z):
X -= 1
Y -= 1
Z -= 1
if N == 4:
return solve4(X, Y, Z)
elif N == 8:
return solve8(X, Y, Z)
elif N == 16:
return solve16(X, Y, Z)
def solve8(X, Y, Z):
aux = [[0, 0, 48, 48, 16, 16, 32, 32] for i in range(4)]
aux += [[48, 48, 0, 0, 32, 32, 16, 16] for i in range(4)]
z = (Z // 16) * 16
rotate_aux(z, X, Y, aux)
magic4 = solve4(X % 4, Y % 4, Z % 16)
magic8 = merge(magic4, aux)
return magic8
def solve16(X, Y, Z):
aux = [[0, 0, 0, 0, 192, 192, 192, 192, 64, 64, 64, 64, 128, 128, 128, 128] for i in range(8)]
aux += [[192, 192, 192, 192, 0, 0, 0, 0, 128, 128, 128, 128, 64, 64, 64, 64] for i in range(8)]
z = (Z // 64) * 64
rotate_aux(z, X, Y, aux)
magic8 = solve8(X % 8, Y % 8, Z % 64)
magic16 = merge(magic8, aux)
return magic16
def rotate_aux(z, x, y, aux):
n = len(aux) - 1
if aux[y][x] == z:
return
elif aux[n - y][x] == z:
aux.reverse()
return
elif aux[y][n - x] == z:
reverseLR(aux)
return
elif aux[n - y][n - x] == z:
aux.reverse()
reverseLR(aux)
return
raise RuntimeError('Unexpected aux and z, x, y')
def merge(magic, aux):
n = len(aux)
m = len(magic)
for y in range(n):
for x in range(n):
aux[y][x] += magic[y % m][x % m]
return aux
def solve4(x, y, z):
''' x, y 位置の値がzである 4 x 4 魔方陣を返す。 位置(p)に応じて処理を振り分け。
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
'''
p = 4 * y + x
if p == 0:
return solve_corner(z)
if p == 3:
magic = solve_corner(z)
reverseLR(magic)
return magic
if p == 12:
magic = solve_corner(z)
magic.reverse()
return magic
if p == 15:
magic = solve_corner(z)
magic.reverse()
reverseLR(magic)
return magic
if p == 1:
return solve_edge(z)
if p == 2:
magic = solve_edge(z)
reverseLR(magic)
return magic
if p == 4:
magic = solve_edge(z)
return transpose(magic)
if p == 7:
magic = solve_edge(z)
magic.reverse()
return transpose(magic)
if p == 8:
magic = solve_edge(z)
reverseLR(magic)
return transpose(magic)
if p == 11:
magic = solve_edge(z)
reverseLR(magic)
magic.reverse()
return transpose(magic)
if p == 13:
magic = solve_edge(z)
magic.reverse()
return magic
if p == 14:
magic = solve_edge(z)
magic.reverse()
reverseLR(magic)
return magic
if p == 5:
magic = solve_inside(z)
return magic
if p == 6:
magic = solve_inside(z)
reverseLR(magic)
return magic
if p == 9:
magic = solve_inside(z)
magic.reverse()
return magic
if p == 10:
magic = solve_inside(z)
magic.reverse()
reverseLR(magic)
return magic
def reverseLR(mat):
for row in mat:
row.reverse()
def transpose(mat):
return list(zip(*mat))
def solve_corner(z):
return solve_012(z, 0, 1, 2)
def solve_edge(z):
return solve_012(z, 1, 0, 2)
def solve_inside(z):
return solve_012(z, 2, 0, 1)
def solve_012(z, p, q, r):
a = [-1] * 3
used = [False] * 16
a[p] = z
used[z] = True
for aq in range(16):
if used[aq]:
continue
a[q] = aq
used[aq] = True
for ar in range(16):
if used[ar]:
continue
a[r] = ar
used[ar] = True
magic = fill_magic(used, a)
if magic:
return magic
used[ar] = False
used[aq] = False
return False
def fill_magic(used, a):
''' 以下の順番で 4 x 4 の魔方陣に数字を入れていく。[]内は、計算で求まる部分。
0 1 3 [4]
12 2 7 [14]
[13] 9 5 [15]
[11][10] [8] [6]
'''
s = sum(range(16)) // 4
a0, a1, a2 = a
for a3 in range(max(0, 16 - a0 - a1), min(16, 31 - a0 - a1)):
a4 = s - a0 - a1 - a3
if used[a3] or used[a4] or not valid([a0, a1, a3, a4]):
continue
used[a3] = True
used[a4] = True
for a5 in range(max(0, 16 - a0 - a2), min(16, 31 - a0 - a2)):
a6 = s - a0 - a2 - a5
if used[a5] or used[a6] or not valid([a0, a2, a5, a6]):
continue
used[a5] = True
used[a6] = True
for a7 in range(max(0, 16 - a3 - a5), min(16, 31 - a3 - a5)):
a8 = s - a3 - a7 - a5
if used[a7] or used[a8] or not valid([a3, a7, a5, a8]):
continue
used[a7] = True
used[a8] = True
for a9 in range(max(0, 16 - a1 - a2, 16 - a4 - a7), min(16, 31 - a1 - a2, 31 - a4 - a7)):
a10 = s - a1 - a2 - a9
a11 = s - a4 - a7 - a9
if used[a9] or used[a10] or used[a11]:
continue
if a6 + a8 + a10 + a11 != s:
continue
if not valid([a1, a2, a9, a10]) or not valid([a6, a8, a10, a11]) or not valid([a4, a7, a9, a11]):
continue
used[a9] = True
used[a10] = True
used[a11] = True
for a12 in range(0, 16):
if used[a12]:
continue
a13 = s - a0 - a11 - a12
a14 = s - a2 - a7 - a12
a15 = s - a4 - a6 - a14
if a13 < 0 or a13 > 15 or a14 < 0 or a14 > 15 or a15 < 0 or a15 > 15:
continue
if used[a13] or used[a14] or used[a15]:
continue
magic = [[a0+1, a1+1, a3+1, a4+1],
[a12+1, a2+1, a7+1, a14+1],
[a13+1, a9+1, a5+1, a15+1],
[a11+1, a10+1, a8+1, a6+1]]
return magic
used[a9] = False
used[a10] = False
used[a11] = False
used[a7] = False
used[a8] = False
used[a5] = False
used[a6] = False
used[a3] = False
used[a4] = False
return False
def valid(lst):
pows = [2, 2, 2, 2]
for i, p in enumerate([1, 2, 4, 8]):
for a in lst:
if a & p:
if pows[i]:
pows[i] -= 1
else:
return False
return not any(pows)
def print_mat(mat):
for row in mat:
print(*row)
if __name__ == '__main__':
N, X, Y, Z = read_data()
magic = solve(N, X, Y, Z)
print_mat(magic)