結果

問題 No.195 フィボナッチ数列の理解(2)
コンテスト
ユーザー qwewe
提出日時 2025-04-24 12:31:03
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 5,278 bytes
コンパイル時間 253 ms
コンパイル使用メモリ 82,420 KB
実行使用メモリ 849,172 KB
最終ジャッジ日時 2025-04-24 12:32:36
合計ジャッジ時間 4,220 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 1 MLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

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

    # Precompute Fibonacci numbers up to fib[45]
    fib = [0, 1, 1]
    for i in range(3, 46):
        fib.append(fib[i-1] + fib[i-2])

    candidates = []

    def check_pair(num1, num2, remaining):
        for i in range(1, 46):
            if i == 1:
                a = 1
                b = 0
            elif i == 2:
                a = 0
                b = 1
            else:
                if i-2 >= len(fib):
                    continue
                a = fib[i-2]
                b = fib[i-1]
            for j in range(1, 46):
                if j == 1:
                    c = 1
                    d = 0
                elif j == 2:
                    c = 0
                    d = 1
                else:
                    if j-2 >= len(fib):
                        continue
                    c = fib[j-2]
                    d = fib[j-1]
                # Calculate determinant
                det = a * d - b * c
                if det != 0:
                    # Check if equations are solvable
                    A_num = d * num1 - b * num2
                    B_num = a * num2 - c * num1
                    if A_num % det != 0 or B_num % det != 0:
                        continue
                    A = A_num // det
                    B = B_num // det
                    if A > 0 and B > 0:
                        # Check if remaining is in the sequence
                        found = False
                        for k in range(1, 46):
                            if k == 1:
                                val = A
                            elif k == 2:
                                val = B
                            else:
                                if k-2 >= len(fib):
                                    continue
                                f_prev_prev = fib[k-2]
                                f_prev = fib[k-1]
                                val = f_prev_prev * A + f_prev * B
                            if val == remaining:
                                found = True
                                break
                            if val > remaining:
                                break
                        if found:
                            candidates.append((A, B))
                else:
                    # Handle det == 0 case
                    if a * num2 != c * num1:
                        continue
                    # Solve aA + bB = num1
                    if a == 0 and b == 0:
                        continue
                    if a == 0:
                        if num1 % b != 0:
                            continue
                        B_val = num1 // b
                        if B_val <= 0:
                            continue
                        # A can be any positive integer, but we need to check remaining
                        # This case is complex, skip for now
                        continue
                    if b == 0:
                        if num1 % a != 0:
                            continue
                        A_val = num1 // a
                        if A_val <= 0:
                            continue
                        # B can be any positive integer, skip
                        continue
                    # General case: aA + bB = num1
                    max_A = (num1 - b) // a
                    if max_A <= 0:
                        continue
                    for A_val in range(1, max_A + 1):
                        rem = num1 - a * A_val
                        if rem <= 0:
                            continue
                        if rem % b != 0:
                            continue
                        B_val = rem // b
                        if B_val <= 0:
                            continue
                        # Check if this (A_val, B_val) satisfies the second equation
                        # Since det is 0, equations are multiples, so it's already satisfied
                        # Now check if remaining is present
                        found = False
                        for k in range(1, 46):
                            if k == 1:
                                val = A_val
                            elif k == 2:
                                val = B_val
                            else:
                                if k-2 >= len(fib):
                                    continue
                                f_prev_prev = fib[k-2]
                                f_prev = fib[k-1]
                                val = f_prev_prev * A_val + f_prev * B_val
                            if val == remaining:
                                found = True
                                break
                            if val > remaining:
                                break
                        if found:
                            candidates.append((A_val, B_val))

    check_pair(X, Y, Z)
    check_pair(X, Z, Y)
    check_pair(Y, Z, X)

    if not candidates:
        print(-1)
        return

    # Find the candidate with minimal A, then B
    candidates.sort(key=lambda x: (x[0], x[1]))
    print(candidates[0][0], candidates[0][1])

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