結果

問題 No.195 フィボナッチ数列の理解(2)
ユーザー 👑 kmjpkmjp
提出日時 2015-02-16 01:20:06
言語 Python2
(2.7.18)
結果
AC  
実行時間 15 ms / 5,000 ms
コード長 1,497 bytes
コンパイル時間 533 ms
コンパイル使用メモリ 6,692 KB
実行使用メモリ 6,132 KB
最終ジャッジ日時 2023-09-06 01:33:58
合計ジャッジ時間 2,528 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 14 ms
5,972 KB
testcase_01 AC 14 ms
6,084 KB
testcase_02 AC 14 ms
6,036 KB
testcase_03 AC 14 ms
5,980 KB
testcase_04 AC 14 ms
5,880 KB
testcase_05 AC 14 ms
5,936 KB
testcase_06 AC 14 ms
5,848 KB
testcase_07 AC 14 ms
6,056 KB
testcase_08 AC 14 ms
5,948 KB
testcase_09 AC 14 ms
5,932 KB
testcase_10 AC 13 ms
5,928 KB
testcase_11 AC 15 ms
6,052 KB
testcase_12 AC 14 ms
5,996 KB
testcase_13 AC 13 ms
6,048 KB
testcase_14 AC 14 ms
6,056 KB
testcase_15 AC 14 ms
6,032 KB
testcase_16 AC 14 ms
6,132 KB
testcase_17 AC 14 ms
5,860 KB
testcase_18 AC 14 ms
6,076 KB
testcase_19 AC 14 ms
5,864 KB
testcase_20 AC 14 ms
5,940 KB
testcase_21 AC 13 ms
6,036 KB
testcase_22 AC 14 ms
5,880 KB
testcase_23 AC 13 ms
5,852 KB
testcase_24 AC 13 ms
5,924 KB
権限があれば一括ダウンロードができます

ソースコード

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