No.195 Understanding the Fibonacci Sequence (2)
タグ : / 解いたユーザー数 53
作問者 : 👑
kmjp
Problem Statement
Having understood super Fibonacci sequences, yuki-kun decided to deepen his understanding of the simple Fibonacci sequence again.
This time, consider the (A,B)-Fibonacci sequence generated from positive integers A,B.
Its first two terms are A,B, and from the third term onward, each term is the sum of the previous two terms, as in the ordinary Fibonacci sequence.
Formally, the k-th term \(F_{A,B}(k)\) of the (A,B)-Fibonacci sequence is defined as follows.
- \(F_{A,B}(1) = A\)
- \(F_{A,B}(2) = B\)
- For \(k \ge 3\), \(F_{A,B}(k) = F_{A,B}(k-1) + F_{A,B}(k-2)\)
Looking around, yuki-kun noticed three positive integers X,Y,Z.
Find a pair of positive integers A,B such that the (A,B)-Fibonacci sequence contains all of X,Y,Z (that is, there exist positive integers \(i,j,k\) such that \(F_{A,B}(i)=X, F_{A,B}(j)=Y, F_{A,B}(k)=Z\)).
If multiple pairs (A,B) satisfy the condition, answer the one with the smallest A. If multiple such pairs have the smallest A, answer the one with the smallest B among them.
If no pair (A,B) satisfies the condition, output -1.
Input
\(X\) \(Y\) \(Z\)
\(X, Y, Z\) are integers satisfying \(1 \le X, Y, Z \le 10^9\).
Output
If A,B satisfying the conditions of the problem statement exist, output A,B on one line, separated by a space.
Otherwise, output -1.
Sample
Sample 1
Input
5 13 34
Output
1 1
The (1,1)-Fibonacci sequence is the same as the ordinary Fibonacci sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
The (2,3)-Fibonacci sequence and the (5,8)-Fibonacci sequence also contain the three input values, but as explained in the problem statement, the answer is (1, 1), which has the smallest A.
Sample 2
Input
11 11 11
Output
1 3
The (1,3)-Fibonacci sequence is 1, 3, 4, 7, 11, 18, ...
Note that 11 does not need to appear three times in the sequence.
Note also that, in other test cases as well, X,Y,Z do not need to appear in this order in the sequence.
Sample 3
Input
5 6 9
Output
-1
Sample 4
Input
35169 76228629 17995137
Output
5487 14841
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。