結果

問題 No.223 1マス指定の魔方陣
コンテスト
ユーザー rpy3cpp
提出日時 2015-06-08 12:02:15
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
RE  
実行時間 -
コード長 3,641 bytes
コンパイル時間 200 ms
コンパイル使用メモリ 13,056 KB
実行使用メモリ 11,392 KB
最終ジャッジ日時 2024-07-06 14:44:41
合計ジャッジ時間 2,730 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 36 RE * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

import itertools

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:
        for row in aux:
            row.reverse()
        return
    elif aux[n - y][n - x] == z:
        aux.reverse()
        for row in aux:
            row.reverse()
        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 transpose(mat):
    return list(zip(*mat))

def solve4(x, y, Z):
    A = [[1, 1, 0, 0], [0, 0, 1, 1], [1, 1, 0, 0], [0, 0, 1, 1]]
    B = [[1, 0, 1, 0], [0, 1, 0, 1], [0, 1, 0, 1], [1, 0, 1, 0]]
    C = [[1, 1, 0, 0], [0, 0, 1, 1], [0, 0, 1, 1], [1, 1, 0, 0]]
    D = [[1, 1, 0, 0], [1, 0, 1, 0], [0, 1, 0, 1], [0, 0, 1, 1]]
    E = [[0, 1, 0, 1], [1, 1, 0, 0], [0, 0, 1, 1], [1, 0, 1, 0]]
    mats = [A, B, C, D, E]

    pow2s = [n for n in [1, 2, 4, 8] if n & Z]
    other = [n for n in [1, 2, 4, 8] if not n & Z]
    selected_mats = select_mat(len(pow2s), x, y, mats)
    coefs = []
    for mat in selected_mats:
        if mat[y][x]:
            coefs.append(pow2s[-1])
            del pow2s[-1]
        else:
            coefs.append(other[-1])
            del other[-1]
    magic = build_magic(selected_mats, coefs)
    return magic

def select_mat(n, X, Y, mats):
    for A, B in itertools.combinations(mats, 2):
        if A[Y][X] + A[X][Y] + B[Y][X] + B[X][Y] == n:
            C = transpose(A)
            D = transpose(B)
            if is_valid(A, B, C, D):
                return A, B, C, D
    for A, B in itertools.combinations(mats, 2):
        if A[3 - Y][X] + A[X][3 - Y] + B[3 - Y][X] + B[X][3 - Y] == n:
            C = transpose(A)
            D = transpose(B)
            if is_valid(A, B, C, D):
                A.reverse()
                B.reverse()
                C.reverse()
                D.reverse()
                return A, B, C, D
    raise RuntimeError('Unexpected xyz combinations!')

def is_valid(A, B, C, D):
    mats = [A, B, C, D]
    magic = build_magic(mats, [8, 4, 2, 1])
    pool = set()
    for row in magic:
        pool |= set(row)
    return len(pool) == 16

def build_magic(selected_mats, coefs):
    magic = [[1] * 4 for i in range(4)]
    for mat, coef in zip(selected_mats, coefs):
        for r in range(4):
            for c in range(4):
                magic[r][c] += mat[r][c] * coef
    return magic

if __name__ == '__main__':
    N, X, Y, Z = read_data()
    magic = solve(N, X, Y, Z)
    for row in magic:
        print(*row)
0