結果
| 問題 |
No.195 フィボナッチ数列の理解(2)
|
| コンテスト | |
| ユーザー |
 gew1fw
|
| 提出日時 | 2025-06-12 20:24:35 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,866 bytes |
| コンパイル時間 | 193 ms |
| コンパイル使用メモリ | 81,784 KB |
| 実行使用メモリ | 487,256 KB |
| 最終ジャッジ日時 | 2025-06-12 20:24:47 |
| 合計ジャッジ時間 | 6,656 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | -- * 3 |
| other | AC * 1 TLE * 1 -- * 20 |
ソースコード
def main():
import sys
X, Y, Z = map(int, sys.stdin.readline().split())
K = X
if X == Y == Z:
# Handle the case where all three are equal
candidates = []
# Precompute a and b up to n=60
a = [0] * 61
b = [0] * 61
a[1] = 1
b[1] = 0
a[2] = 0
b[2] = 1
for n in range(3, 61):
a[n] = a[n-1] + a[n-2]
b[n] = b[n-1] + b[n-2]
for n in range(1, 61):
an = a[n]
bn = b[n]
if an == 0 and bn == 0:
continue
if an == 0:
# Equation: 0*A + 1*B = K
B_val = K
A_val = 1 # minimal A is 1
# Check if K is in the sequence
seq = [A_val, B_val]
for i in range(2, 60):
next_term = seq[i-1] + seq[i-2]
if next_term > 1e18:
break
seq.append(next_term)
found = False
for term in seq:
if term == K:
found = True
break
if found:
candidates.append( (A_val, B_val) )
elif bn == 0:
# Equation: 1*A + 0*B = K
A_val = K
B_val = 1 # minimal B is 1
# Check if K is in the sequence
seq = [A_val, B_val]
for i in range(2, 60):
next_term = seq[i-1] + seq[i-2]
if next_term > 1e18:
break
seq.append(next_term)
found = False
for term in seq:
if term == K:
found = True
break
if found:
candidates.append( (A_val, B_val) )
else:
# Iterate A to find possible B
max_A = K // an + 1 if an != 0 else 1
for A_val in range(1, max_A + 1):
numerator = K - an * A_val
if numerator <= 0:
continue
if numerator % bn != 0:
continue
B_val = numerator // bn
if B_val <= 0:
continue
# Check if K is in the sequence
seq = [A_val, B_val]
for i in range(2, 60):
next_term = seq[i-1] + seq[i-2]
if next_term > 1e18:
break
seq.append(next_term)
found = False
for term in seq:
if term == K:
found = True
break
if found:
candidates.append( (A_val, B_val) )
if not candidates:
print(-1)
return
# Sort to find minimal A, then B
candidates.sort()
a_min, b_min = candidates[0]
print(a_min, b_min)
return
else:
# General case
# Precompute a and b up to n=60
a = [0] * 61
b = [0] * 61
a[1] = 1
b[1] = 0
a[2] = 0
b[2] = 1
for n in range(3, 61):
a[n] = a[n-1] + a[n-2]
b[n] = b[n-1] + b[n-2]
candidates = []
pairs = [(X, Y), (X, Z), (Y, Z)]
for P, Q in pairs:
for i in range(1, 60):
for j in range(i+1, 61):
ai = a[i]
bi = b[i]
aj = a[j]
bj = b[j]
D = ai * bj - aj * bi
if D == 0:
if P == Q:
# Solve ai*A + bi*B = P
# Express B = (P - ai*A) / bi
# Iterate A to find integer B
max_A = P // ai + 1 if ai != 0 else 1
for A_val in range(1, max_A + 1):
numerator = P - ai * A_val
if numerator <= 0:
continue
if bi == 0:
continue
if numerator % bi != 0:
continue
B_val = numerator // bi
if B_val <= 0:
continue
# Check if all three are in the sequence
seq = [A_val, B_val]
for k in range(2, 60):
next_term = seq[k-1] + seq[k-2]
if next_term > 1e18:
break
seq.append(next_term)
found = True
for num in [X, Y, Z]:
if num not in seq:
found = False
break
if found:
candidates.append( (A_val, B_val) )
continue
else:
A_num = P * bj - Q * bi
B_num = Q * ai - P * aj
if A_num % D != 0 or B_num % D != 0:
continue
A = A_num // D
B = B_num // D
if A <= 0 or B <= 0:
continue
# Generate the sequence
seq = [A, B]
for k in range(2, 60):
next_term = seq[k-1] + seq[k-2]
if next_term > 1e18:
break
seq.append(next_term)
# Check if all three are present
found = True
for num in [X, Y, Z]:
if num not in seq:
found = False
break
if found:
candidates.append( (A, B) )
if not candidates:
print(-1)
return
# Remove duplicates and sort
unique_candidates = list(set(candidates))
unique_candidates.sort()
a_min, b_min = unique_candidates[0]
print(a_min, b_min)
if __name__ == "__main__":
main()