Cerința

Numim suma cifrelor până la o cifră a unui număr X, o valoare mai mică decât 10 obținută prin adunarea cifrelor numărului X și repetarea procedurii dacă suma obținută este mai mare decât 10, de această dată având drept X suma obținută la pasul precedent.

Se dă un număr n reprezentând poziția unui număr Fn din șirul lui Fibonacci. Să se calculeze suma cifrelor până la o cifră a lui Fn.

Reamintim că primele două numere din șirul lui Fibonacci au valoarea 1, iar restul se obțin ca fiind suma precedentelor două (pentru orice poziție n mai mare strict decât 2, Fn = Fn-1 + Fn-2).

Date de intrare

Programul citește de la tastatură numărul n.

Date de ieșire

Programul va afișa pe ecran valoarea S, reprezentând suma cifrelor până la o cifră a numărului Fn.

Restricții și precizări

• 1 ≤ n ≤ 1019

Exemplu

Intrare

11

Ieșire

8

Explicație

Al unsprezecelea număr din șirul lui Fibonacci este 89 (1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…). Adunând cifrele acestuia obținem 17. Deoarece 17 este mai mare decât 10 se adună și cifrele acestuia: 1+7=8.

#include <bits/stdc++.h>
using namespace std;
int main()
{
    unsigned long long n , a , b , c , s = 0;
    cin >> n;
    if(n == 1) cout << 1;
    else if(n == 2) cout << 1;
    else
    {
        if(n > 24) n %= 24;
        a = 1 , b = 1;
        for(int i = 3 ; i <= n ; i++)
        {
            c = a + b;
            a = b;
            b = c;
        }
        cout << c% 9;
    }
}