結果

問題 No.195 フィボナッチ数列の理解(2)
ユーザー gew1fw
提出日時 2025-06-12 15:19:48
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 3,973 bytes
コンパイル時間 520 ms
コンパイル使用メモリ 82,444 KB
実行使用メモリ 849,276 KB
最終ジャッジ日時 2025-06-12 15:20:08
合計ジャッジ時間 4,468 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 1 MLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    X, Y, Z = map(int, sys.stdin.readline().split())

    # Precompute a and b arrays
    max_n = 60
    a = [0] * (max_n + 1)
    b = [0] * (max_n + 1)

    # Compute a_n
    a[1] = 1
    a[2] = 0
    for n in range(3, max_n + 1):
        a[n] = a[n-1] + a[n-2]

    # Compute b_n = fib(n-1)
    fib = [0] * (max_n + 1)
    fib[0] = 0
    fib[1] = 1
    for n in range(2, max_n + 1):
        fib[n] = fib[n-1] + fib[n-2]
    for n in range(1, max_n + 1):
        b[n] = fib[n-1]

    candidates = []

    if X == Y == Z:
        V = X
        for p in range(1, max_n + 1):
            a_p = a[p]
            b_p = b[p]
            if a_p == 0 and b_p == 0:
                continue
            if a_p == 0:
                if V % b_p != 0:
                    continue
                B = V // b_p
                if B <= 0:
                    continue
                A = 0
                continue
            if b_p == 0:
                if V % a_p != 0:
                    continue
                A = V // a_p
                if A <= 0:
                    continue
                B = 0
                continue

            max_B = V // b_p
            for B in range(1, max_B + 1):
                remainder = V - b_p * B
                if remainder % a_p != 0:
                    continue
                A = remainder // a_p
                if A <= 0:
                    continue

                generate_f = [0] * (max_n + 1)
                generate_f[1] = A
                generate_f[2] = B
                found = False
                for i in range(3, max_n + 1):
                    generate_f[i] = generate_f[i-1] + generate_f[i-2]
                    if generate_f[i] > V:
                        break
                for i in range(1, max_n + 1):
                    if generate_f[i] == V:
                        found = True
                        break
                    if generate_f[i] > V:
                        break
                if found:
                    candidates.append((A, B))
    else:
        pairs = [(X, Y), (X, Z), (Y, Z)]
        for V1, V2 in pairs:
            for p in range(1, max_n + 1):
                a_p = a[p]
                b_p = b[p]
                for q in range(p + 1, max_n + 1):
                    a_q = a[q]
                    b_q = b[q]

                    D = a_p * b_q - a_q * b_p
                    if D == 0:
                        continue

                    numerator_A = V1 * b_q - V2 * b_p
                    if numerator_A % D != 0:
                        continue
                    A = numerator_A // D

                    numerator_B = V2 * a_p - V1 * a_q
                    if numerator_B % D != 0:
                        continue
                    B = numerator_B // D

                    if A <= 0 or B <= 0:
                        continue

                    if V1 == X and V2 == Y:
                        third = Z
                    elif V1 == X and V2 == Z:
                        third = Y
                    else:
                        third = X

                    generate_f = [0] * (max_n + 1)
                    generate_f[1] = A
                    generate_f[2] = B
                    found = False
                    for i in range(3, max_n + 1):
                        generate_f[i] = generate_f[i-1] + generate_f[i-2]
                        if generate_f[i] > third:
                            break
                    for i in range(1, max_n + 1):
                        if generate_f[i] == third:
                            found = True
                            break
                        if generate_f[i] > third:
                            break
                    if found:
                        candidates.append((A, B))

    if not candidates:
        print(-1)
    else:
        candidates.sort()
        A, B = candidates[0]
        print(A, B)

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