Challenge: Fibonacci

Lab C++ Intermediate 20 points

The Fibonacci numbers start 0 1 1 2 3 5 8 ...: each one is the sum of the two before it. Write a function long long fib(int n) that returns the n-th one (fib(0) = 0, fib(1) = 1). Read n and print fib(n).

Input

One integer n (0 to 80).

Output

fib(n).

Example

Input

Output

Sample input available Sample output available

Editor

C++

Hints

Keep the last two numbers in two variables.

A recursive fib is easy to write but too slow for n = 80. Use a loop.

The answers get big: use long long.

Solution explanation

Two variables walk along the sequence. Each step the pair (a, b) becomes (b, a + b).

Show solution

#include <iostream>
using namespace std;

long long fib(int n) {
    long long a = 0, b = 1;
    for (int i = 0; i < n; i++) {
        long long next = a + b;
        a = b;
        b = next;
    }
    return a;
}

int main() {
    int n;
    cin >> n;
    cout << fib(n) << "\n";
    return 0;
}

Output

Answer