`[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© = Fc−1 ∗ x + Fc ∗ y (6)

and in case of negative c, we can make it positive by adding abs© + 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©

cout << fib[c] * y + fib[c - 1] * x << endl;

}

return 0;

}