#992008 (PyPy3) No.2797 Square Tile

• 問題: No.2797 Square Tile
• ユーザー: navel_tos
• 提出日時: 2024-06-29 15:17:23
• 言語: PyPy3 (7.3.15)
• 結果: AC
• 実行時間: 78 ms / 2,000 ms
• コード長: 3,628 bytes
• コンパイル時間: 127 ms
• コンパイル使用メモリ: 82,320 KB
• 実行使用メモリ: 79,388 KB
• 最終ジャッジ日時: 2024-06-29 15:17:27
• 合計ジャッジ時間: 3,090 ms
• ジャッジサーバーID （参考情報）: judge5 / judge1

ファイルパターン	結果
sample	AC * 2
other	AC * 21

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#yukicoder 2797 Square Tile
import random, math
#愚直判定
def check(A, B, A_list, B_list):
    L = A ** 2 + B ** 2
    if not len(A_list) == len(B_list) == L:
        return False
    if not all(i in range(L) and j in range(L) for i, j in A_list + B_list):
        return False
    D = [[0] * L for _ in range(L)]
    for i, j in A_list:
        for x in range(i, i + A):
            x %= L
            for y in range(j, j + A):
                y %= L
                if D[x][y] == 1: return False
                D[x][y] = 1
    for i, j in B_list:
        for x in range(i, i + B):
            x %= L
            for y in range(j, j + B):
                y %= L
                if D[x][y] == 1: return False
                D[x][y] = 1
    return True
#タイルA_listが定められていると仮定する。B_listを愚直に作成せよ。
def fill(A, B, A_list):
    L = A ** 2 + B ** 2
    if not len(A_list) == L:
        return []
    if not all(i in range(L) and j in range(L) for i, j in A_list):
        return []
    D = [[0] * L for _ in range(L)]
    for i, j in A_list:
        for x in range(i, i + A):
            x %= L
            for y in range(j, j + A):
                y %= L
                if D[x][y] == 1: return []
                D[x][y] = 1
    B_list = []
    while len(B_list) < L:
        for i in range(L):
            for j in range(L):
                if D[i][j] == 0 and D[(i - 1) % L][j] == D[i][(j - 1) % L] == 1:
                    B_list.append((i, j))
                    for x in range(i, i + B):
                        x %= L
                        for y in range(j, j + B):
                            y %= L
                            if D[x][y] == 1: return []
                            D[x][y] = 1
    return B_list
#乱択解法
def solve_random(A, B):
    L = A ** 2 + B ** 2
    while True:
        A_list = [(random.randint(0, L - 1), random.randint(0, L - 1))
                  for _ in range(L - 1)] + [(0, 0)]
        B_list = fill(A, B, A_list)
        if len(B_list) == L:
            assert check(A, B, A_list, B_list)
            visualize(A, B, A_list, B_list)
            return A_list, B_list
def visualize(A, B, A_list, B_list):
    L = A ** 2 + B ** 2
    D = [[None] * L for _ in range(L)]
    for i, j in A_list:
        for x in range(i, i + A):
            x %= L
            for y in range(j, j + A):
                y %= L
                D[x][y] = 'a'
        D[i][j] = 'A'
    for i, j in B_list:
        for x in range(i, i + B):
            x %= L
            for y in range(j, j + B):
                y %= L
                D[x][y] = 'b'
        D[i][j] = 'B'
    for d in D:
        print(''.join(d))
#実験結果を採用
#答えとなる盤面を出力せよ。
def solve(A, B):
    L = A ** 2 + B ** 2
    if math.gcd(A, B) == 1:
        A_list = []
        B_list = []
        for i in range(L):
            A_list.append((A * i % L, B * i % L))
            B_list.append((A * (i + 1) % L, B * i % L))
        return A_list, B_list
    else:
        G = math.gcd(A, B)
        H = L // G
        a_list, b_list = solve(A // G, B // G)
        A_list = [(H * i + G * x, H * j + G * y)
                  for x, y in a_list for i in range(G) for j in range(G)]
        B_list = [(H * i + G * x, H * j + G * y)
                  for x, y in b_list for i in range(G) for j in range(G)]
        return A_list, B_list
    
def test(A, B):
    A_list, B_list = solve(A, B)
    visualize(A, B, A_list, B_list)
    
#答えを実行
A, B = map(int, input().split())
A_list, B_list = solve(A, B)
for i, j in A_list + B_list: print(i, j)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX