#31556 (Python3) No.223 1マス指定の魔方陣

提出ソース

結果

問題	No.223 1マス指定の魔方陣
ユーザー	rpy3cpp
提出日時	2015-06-09 17:38:14
言語	Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果	AC
実行時間	20 ms / 5,000 ms
コード長	7,131 bytes
コンパイル時間	73 ms
コンパイル使用メモリ	11,796 KB
実行使用メモリ	9,140 KB
最終ジャッジ日時	2023-09-20 20:22:52
合計ジャッジ時間	3,238 ms
ジャッジサーバーID （参考情報）	judge11 / judge13

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	19 ms 8,936 KB
testcase_01	AC	19 ms 9,124 KB
testcase_02	AC	20 ms 9,048 KB
testcase_03	AC	20 ms 8,940 KB
testcase_04	AC	18 ms 8,956 KB
testcase_05	AC	19 ms 9,088 KB
testcase_06	AC	18 ms 8,988 KB
testcase_07	AC	17 ms 9,088 KB
testcase_08	AC	18 ms 9,124 KB
testcase_09	AC	19 ms 8,936 KB
testcase_10	AC	18 ms 9,112 KB
testcase_11	AC	18 ms 9,088 KB
testcase_12	AC	19 ms 9,084 KB
testcase_13	AC	19 ms 9,140 KB
testcase_14	AC	20 ms 9,020 KB
testcase_15	AC	19 ms 8,948 KB
testcase_16	AC	19 ms 9,028 KB
testcase_17	AC	18 ms 8,952 KB
testcase_18	AC	18 ms 9,032 KB
testcase_19	AC	19 ms 9,080 KB
testcase_20	AC	19 ms 8,992 KB
testcase_21	AC	18 ms 8,964 KB
testcase_22	AC	18 ms 8,992 KB
testcase_23	AC	19 ms 9,124 KB
testcase_24	AC	18 ms 9,128 KB
testcase_25	AC	19 ms 9,028 KB
testcase_26	AC	18 ms 9,056 KB
testcase_27	AC	20 ms 9,112 KB
testcase_28	AC	19 ms 8,984 KB
testcase_29	AC	20 ms 9,112 KB
testcase_30	AC	19 ms 9,092 KB
testcase_31	AC	18 ms 9,056 KB
testcase_32	AC	19 ms 9,112 KB
testcase_33	AC	18 ms 8,940 KB
testcase_34	AC	18 ms 8,964 KB
testcase_35	AC	19 ms 9,036 KB
testcase_36	AC	19 ms 8,964 KB
testcase_37	AC	19 ms 8,988 KB
testcase_38	AC	20 ms 8,960 KB
testcase_39	AC	19 ms 9,076 KB
testcase_40	AC	20 ms 8,992 KB
testcase_41	AC	19 ms 9,028 KB
testcase_42	AC	19 ms 9,028 KB
testcase_43	AC	20 ms 9,032 KB
testcase_44	AC	19 ms 8,948 KB
testcase_45	AC	19 ms 8,984 KB
testcase_46	AC	20 ms 9,024 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

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)

yukicoder

結果

テストケース

ソースコード