結果

問題 No.3094 Stapler
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 13:03:26
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 5,013 bytes
コンパイル時間 381 ms
コンパイル使用メモリ 82,348 KB
実行使用メモリ 89,276 KB
最終ジャッジ日時 2025-10-23 22:38:40
合計ジャッジ時間 12,123 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other RE * 72
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from fractions import Fraction

def main():
    N = int(sys.stdin.readline())
    matrix = []
    missing_i = -1
    missing_j = -1
    for i in range(N):
        row = sys.stdin.readline().split()
        for j in range(N):
            if row[j] == '?':
                missing_i = i
                missing_j = j
        matrix.append(row)
    
    for k in range(N):
        valid_col = True
        sum_sq_identity = 0
        missing_in_k = (missing_j == k)
        
        if missing_in_k:
            for row in range(N):
                val = matrix[row][k]
                if val == '?':
                    continue
                else:
                    val_int = int(val)
                    if val_int <= 0:
                        valid_col = False
                        break
                    sum_sq_identity += val_int * val_int
            if not valid_col:
                continue
        else:
            for row in range(N):
                val = matrix[row][k]
                if val == '?':
                    valid_col = False
                    break
                val_int = int(val)
                if val_int <= 0:
                    valid_col = False
                    break
                sum_sq_identity += val_int * val_int
            if not valid_col:
                continue
        
        if missing_in_k:
            sum_terms_fraction = Fraction(0, 1)
            valid = True
            for j in range(N):
                if j == k:
                    continue
                S_j = 0
                for row in range(N):
                    val = matrix[row][j]
                    S_j += int(val) * int(val)
                if S_j == 0:
                    valid = False
                    break
                sum_terms_fraction += Fraction(1, S_j)
            if not valid:
                continue
            D_fraction = Fraction(1, 1) - sum_terms_fraction
            if D_fraction == 0:
                continue
            try:
                rhs = 1 / D_fraction
            except ZeroDivisionError:
                continue
            if rhs.denominator != 1:
                continue
            rhs_val = rhs.numerator
            x_squared = rhs_val - sum_sq_identity
            if x_squared < 0:
                continue
            x = int(x_squared ** 0.5)
            if x * x != x_squared:
                continue
            if x <= 0:
                continue
            G = sum_sq_identity + x_squared
            valid = True
            for j in range(N):
                if j == k:
                    continue
                S_j = 0
                for row in range(N):
                    val = matrix[row][j]
                    S_j += int(val) * int(val)
                if G % S_j != 0:
                    valid = False
                    break
            if not valid:
                continue
            sum_cj = 1
            for j in range(N):
                if j == k:
                    continue
                S_j = 0
                for row in range(N):
                    val = matrix[row][j]
                    S_j += int(val) * int(val)
                sum_cj += G // S_j
            if sum_cj == G:
                print(x)
                return
        else:
            j_missing = missing_j
            sum_sq_j_other = 0
            for row in range(N):
                val = matrix[row][j_missing]
                if val == '?':
                    continue
                sum_sq_j_other += int(val) * int(val)
            sum_other = 0
            valid = True
            for j in range(N):
                if j == k or j == j_missing:
                    continue
                S_j = 0
                for row in range(N):
                    val = matrix[row][j]
                    if val == '?':
                        valid = False
                        break
                    S_j += int(val) * int(val)
                if not valid or S_j == 0:
                    valid = False
                    break
                if sum_sq_identity % S_j != 0:
                    valid = False
                    break
                sum_other += sum_sq_identity // S_j
            if not valid:
                continue
            G = sum_sq_identity
            R = G - sum_other - 1
            if R <= 0:
                continue
            if G % R != 0:
                continue
            required = G // R
            x_squared = required - sum_sq_j_other
            if x_squared < 0:
                continue
            x = int(x_squared ** 0.5)
            if x * x != x_squared:
                continue
            S_j_missing = sum_sq_j_other + x_squared
            if S_j_missing == 0:
                continue
            if G % S_j_missing != 0:
                continue
            sum_cj = 1 + sum_other + (G // S_j_missing)
            if sum_cj == G:
                print(x)
                return

if __name__ == "__main__":
    main()
0