結果

問題 No.195 フィボナッチ数列の理解(2)
コンテスト
ユーザー lam6er
提出日時 2025-04-09 21:02:54
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,966 bytes
コンパイル時間 461 ms
コンパイル使用メモリ 82,904 KB
実行使用メモリ 62,932 KB
最終ジャッジ日時 2025-04-09 21:04:37
合計ジャッジ時間 2,416 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

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

    candidates = []

    # Get coefficients for a given k
    def get_coeffs(k):
        if k == 1:
            return (1, 0)
        elif k == 2:
            return (0, 1)
        else:
            if k-2 < 0 or k-1 >= len(fib):
                return (0, 0)
            a = fib[k-2]
            b = fib[k-1]
            return (a, b)

    max_k = 45

    for kx in range(1, max_k+1):
        ax, bx = get_coeffs(kx)
        if ax == 0 and bx == 0:
            continue
        for ky in range(1, max_k+1):
            ay, by = get_coeffs(ky)
            if ay == 0 and by == 0:
                continue

            D = ax * by - ay * bx

            if D != 0:
                numerator_A = X * by - Y * bx
                numerator_B = Y * ax - X * ay
                if numerator_A % D != 0 or numerator_B % D != 0:
                    continue
                A = numerator_A // D
                B = numerator_B // D
                if A > 0 and B > 0:
                    candidates.append((A, B))
            else:
                if (ax * Y != ay * X) or (bx * Y != by * X):
                    continue
                a = ax
                b = bx
                found = False
                min_pair = None

                if a == 0 and b == 0:
                    continue
                elif a == 0:
                    if b == 0:
                        continue
                    if X % b != 0:
                        continue
                    B_candidate = X // b
                    if B_candidate <= 0:
                        continue
                    A_candidate = 1
                    min_pair = (A_candidate, B_candidate)
                elif b == 0:
                    if a == 0:
                        continue
                    if X % a != 0:
                        continue
                    A_candidate = X // a
                    if A_candidate <= 0:
                        continue
                    B_candidate = 1
                    min_pair = (A_candidate, B_candidate)
                else:
                    max_A = (X - b) // a
                    if max_A < 1:
                        continue
                    for A_val in range(1, max_A + 1):
                        rem = X - a * A_val
                        if rem < 0:
                            break
                        if rem % b != 0:
                            continue
                        B_val = rem // b
                        if B_val < 1:
                            continue
                        if min_pair is None or (A_val < min_pair[0]) or (A_val == min_pair[0] and B_val < min_pair[1]):
                            min_pair = (A_val, B_val)
                            break  # break early to find the smallest A
                    if min_pair is None:
                        continue

                if min_pair:
                    A_candidate, B_candidate = min_pair
                    candidates.append((A_candidate, B_candidate))

    # Check Z in the Fibonacci sequence for each candidate (A,B)
    def check_z(A, B, Z_check):
        if A == Z_check or B == Z_check:
            return True
        prev_prev = A
        prev = B
        while True:
            current = prev_prev + prev
            if current == Z_check:
                return True
            if current > Z_check:
                return False
            prev_prev, prev = prev, current

    valid = []
    for A, B in candidates:
        if check_z(A, B, Z):
            valid.append((A, B))

    if not valid:
        print(-1)
        return

    # Sort by A, then B
    valid.sort(key=lambda x: (x[0], x[1]))
    print(valid[0][0], valid[0][1])

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