Cerința

Rică a învățat la școală despre șiruri recurente și a primit ca temă să lucreze cu un anumit șir. Rică știe că primele elemente din acest șir sunt următoarele: 1,1,2,4,7,13,24,44,81,149,274,504. Tema lui Rică este să găsească termenul de pe locul X. Rică nu știa să zică… regula şirului nostru, de aceea el vă cere ajutorul.

Deduceți regula de formare a șirului și scrieți un program care să afișeze pentru un X dat, elementul din șir de pe poziția X.

Date de intrare

Fișierul de intrare rica.in conține pe prima linie valoarea lui X.

Date de ieșire

Fișierul de ieșire rica.out va conține pe prima linie valoarea elementului din şirul dat de pe poziţia X.

Restricții și precizări

• 1 ≤ n ≤ 10.000

Exemple

#include <bits/stdc++.h>


using namespace std;

ifstream cin("rica.in");
ofstream cout("rica.out");

int a[10001] , b[10001] , c[10001] , n , m , p , cop[10001];

void invers(int a[] , int n)
{
    int i = 1 , j = n;
    while(i <= j)
    {
        swap(a[i] , a[n - i + 1]);
        i++;
        j--;
    }
}

void adunare(int a[] , int &n , int b[] , int m)
{
    invers(a , n);
    invers(b , m);
    int t = 0;
    for(int i = 1 ; i <= n ; i++)
    {
        int cu = a[i] + b[i] + t;
        a[i] = cu % 10;
        t = cu / 10;
    }
    if(t > 0) a[++n] = t;
    invers(a , n);
}

void copiere(int a[] , int n , int b[] , int m)
{
    for(int i = 1 ; i <= m ; i++)
        a[i] = b[i];
}
int main()
{
    int x;
    cin >> x;
    if(x == 1 || x == 2) cout << 1;
    else if(x == 3) cout << 2;
    else
    {
        a[1] = 1 , b[1] = 1 , c[1] = 2;
        n = 1 , m = 1 , p = 1;
        for(int i = 4 ; i <= x ; i++)
        {
            for(int i = 1 ; i <= p ; i++) cop[i] = c[i];
            int c1 = n , c2 = m , c3 = p;
            adunare(c , p , b , m);
            adunare(c , p , a , n);
            n = c2 , m = c3;
            copiere(a , n , b , m);
            invers(a , n);
            copiere(b , m , cop , p);
        }
        for(int i = 1 ; i <= p ; i++) cout << c[i];
    }
}