[Problem](https://www.codechef.com/SGOC2019/problems/SGOC19FF)
Contest
Fun with Fibonacci
Difficulty
Medium
Prerequisites
Fibonacci Sequence, Basic Algebra
Problem Statement
You are given two positions a and b with their generalized Fibonacci value Fa
and Fb respectively, using these value you have to find the generalized Fibonacci
value of position c, which is Fc.
Explanation
Fibonacci sequence is a sequence in which each number is the sum of the two
preceding numbers, starting from 0 and 1.
F0 = 0
F1 = 1
Fn = F(n−1) + F(n−2), for integer n > 1.
Based on the above, the sequence is
F0 = 0
F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
So, in the normal Fibonacci sequence we have an initial value of F0 = 0 and
F1 = 1, and that generates the whole Fibonacci sequence, what if we change the
base value?
Let, f(i) is a fibonacci function with f(0) = x and f(1) = y, now if we generate
the fibonacci sequence, then
1
f(0) = x
f(1) = y
f(2) = x + y
f(3) = x + 2 ∗ y
f(4) = 2 ∗ x + 3 ∗ y
f(5) = 3 ∗ x + 5 ∗ y
f(6) = 5 ∗ x + 8 ∗ y . . .
Now, you can see that for any x, y and i
f(i) = Fi−1 ∗ x + Fi ∗ y (1)
where i > 1 and Fi
, Fi−1 are normal fibonacci value.
Using equation (1), we can write
f(a) = Fa−1 ∗ x + Fa ∗ y (2)
f(b) = Fb−1 ∗ x + Fb ∗ y (3)
Using equation (2) and (3), we can find the value of x and y, because we have
given f(a), f(b) in input and we know Fa, Fa−1, Fb and Fb−1 because these are
value of normal fibonacci sequence.
So,
x =
f(b) ∗ Fa − f(a) ∗ Fb
Fb−1 ∗ Fa − Fa−1 ∗ Fb
(4)
and
y =
f(a) − Fa−1 ∗ x
Fa
(5)
Note: {Fb−1 ∗ Fa − Fa−1 ∗ Fb} and {Fa} will never equal to zero according to
normal fibonacci sequence if a, b >= 3, which is given in problem statement.
Using x and y, we can find
f(c) = Fc−1 ∗ x + Fc ∗ y (6)
and in case of negative c, we can make it positive by adding abs(c) + 1 in a and
b, so that c will be 1, and the same method will work for negative values as well.
2
Time Complexity
O(T)
Space Complexity
O(1)
Code
#include <bits/stdc++.h>
#define ll long long
using namespace std;
// Array for fibonacci values
ll fib[71];
// Function to initialize simple fibonacci values
void init()
{
fib[0] = 1;
fib[1] = 1;
for (int i = 2; i < 71; i++)
{
fib[i] = fib[i - 1] + fib[i - 2];
}
}
int main(int argc, char const *argv[])
{
// Initialize simple Fibonacci
init();
ll a, fa, b, fb, x, y, c, t;
cin >> t;
while (t–)
{
// Taking inputs
cin >> a >> fa;
cin >> b >> fb;
3
cin >> c;
// If c <= 0, then make it greater than 0
if (c <= 0)
{
a += (-c) + 1;
b += (-c) + 1;
c = 1;
}
// Calculating x
x = (fb * fib[a] - fib[b] * fa) / (fib[b - 1] * fib[a] - fib[b] * fib[a - 1]);
// Calculating y
y = (fa - fib[a - 1] * x) / fib[a];
// Printing FF(c)
cout << fib[c] * y + fib[c - 1] * x << endl;
}
return 0;
}