No.195 フィボナッチ数列の理解(2)

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 28
作問者 : kmjpkmjp

3 ProblemId : 382 / 出題時の順位表

問題文

スーパーフィボナッチ数列を理解したyuki君は、またシンプルなフィボナッチ数列について理解を深めることにした。

今度は正整数A,Bから生成される(A,B)フィボナッチ数列というものを考える。
これは最初の2項がA,Bで、3項目以降は通常のフィボナッチ数列と同様に直前2項の和となっているものである。
厳密に書くと、(A,B)フィボナッチ数列の第k項\(F_{A,B}(k)\)は以下の通りである。
- \(F_{A,B}(1) = A\)
- \(F_{A,B}(2) = B\)
- \(k \ge 3\)のとき、\(F_{A,B}(k) = F_{A,B}(k-1) + F_{A,B}(k-2)\)

yuki君が周りを見ると、3つの正整数X,Y,Zが目についた。
(A,B)フィボナッチ数列がこれらX,Y,Zすべてを含む(\(F_{A,B}(i)=X, F_{A,B}(j)=Y, F_{A,B}(k)=Z\)となる正整数\(i,j,k\)が存在する)ような正整数A,Bの対を答えよ。
条件を満たす(A,B)の対が複数存在する場合、Aが最小のものを答えよ。Aが最小のものが複数ある場合、その中でBが最小なものを答えよ。
条件を満たす(A,B)の対が存在しない場合、-1を出力せよ。

入力

\(X\) \(Y\) \(Z\)

\(X, Y, Z\)は\(1 \le X, Y, Z \le 10^9\)を満たす整数である。

出力

問題文の条件を満たすA,Bが存在するなら、A,Bを空白切りで1行で出力せよ。
存在しないなら、-1を出力せよ。

サンプル

サンプル1
入力
5 13 34
出力
1 1

(1,1)フィボナッチ数列は普通のフィボナッチ数列と同じで1, 1, 2, 3, 5, 8, 13, 21, 34, ...となる数列である。
(2,3)フィボナッチ数列や(5,8)フィボナッチ数列も入力の3値を含むが、問題文の説明にあるとおりAが最小である(1, 1)を答える。

サンプル2
入力
11 11 11
出力
1 3

(1,3)フィボナッチ数列は1, 3, 4, 7, 11, 18, ...となっている。
数列中に11が3回登場する必要はない点に注意。

他のテストケースでも、X,Y,Zは数列中この順で出てくる必要はないことに注意せよ。

サンプル3
入力
5 6 9
出力
-1

サンプル4
入力
35169 76228629 17995137
出力
5487 14841

提出ページヘ