結果

問題 No.195 フィボナッチ数列の理解(2)
ユーザー kmjp
提出日時 2015-02-16 01:20:06
言語 Python2
(2.7.18)
結果
AC  
実行時間 16 ms / 5,000 ms
コード長 1,497 bytes
コンパイル時間 214 ms
コンパイル使用メモリ 7,068 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-23 20:38:16
合計ジャッジ時間 1,523 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

# -*- coding: utf-8 -*-

# 入力
X = map(int, raw_input().strip().split())

# 重複を取り除く
X = list(set(X))
X.sort()

# (1,0)フィボナッチ数列と(0,1)フィボナッチ数列を作る
F = [ [0,1,0], [0,0,1] ]
for i in range(3,50):
	F[0].append(F[0][i-1]+F[0][i-2])
	F[1].append(F[1][i-1]+F[1][i-2])

if len(X)==1:
	# uniqueな入力が1値の場合、1とXを作ると考えると、２値のケースと同じように考えられる
	X.insert(0,1)

A = B = 10**9
# F[A,B][i]=X[0]かつF[A,B][j]=X[1]となるA,Bを、i,j総当たりで探す
for i in range(1,50):
	for j in range(1,50):
		if i==j:
			continue
		
		# F[A,B][i] = A * F[1,0][i] + B * F[0,1][i] = X[0]
		# F[A,B][j] = A * F[1,0][j] + B * F[0,1][j] = X[1]
		
		# ここからA,Bを連立方程式の要領で求める。
		D = F[0][i]*F[1][j] - F[0][j]*F[1][i]
		
		P = F[1][j]*X[0] - F[1][i]*X[1]
		Q = -F[0][j]*X[0] + F[0][i]*X[1]
		a = P / D
		b = Q / D
		
		# 解が非整数や0以下なら不可
		if P%D != 0 or Q%D != 0 or a<1 or b<1:
			continue
		
		ok = 1
		if len(X)==3:
			# 3項の場合、(a,b)フィボナッチ数列がX[2]を含むかチェック
			ok = 0
			T = [a,b]
			while T[-1] < X[2]:
				T.append(T[-1]+T[-2])
				ok |= T[-1]==X[2]
		
		# 最小なら更新
		if ok and (a < A or (a==A and b<B)):
			A,B = a,b

if A >= 10**9:
	print -1
else:
	print A,B
	
	# 以下確認用のフィボナッチ数生成コード
	#T = [A,B]
	#while T[-1] <= 100000000:
	#	T.append(T[-1]+T[-2])
	#print T
0