Cerința

Fiind dat un număr natural n, se cere să se calculeze suma cifrelor numărului care reprezintă numărul de numere de n cifre formate cu cifrele 3 şi 4.

Date de intrare

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

Date de ieșire

Programul va afișa pe ecran numărul S, reprezentând suma cerută.

Restricții și precizări

• 1 ≤ n ≤ 100.000

Exemplu

Intrare

4

Ieșire

7

Explicație

Numerele de 4 cifre formate cu cifrele 3 şi 4 sunt 3333 , 3334 , 3343 , 3433 , 4333 , 3344 , 3434 , 4334 , 4343 , 4433 , 3443 , 3444 , 4344 , 4434 , 4443 , 4444. Deci sunt 16 numere, iar suma cifrelor este S=7.

#include <bits/stdc++.h>
using namespace std;

int n, a[100001], c=1;

int main()
{
    cin >> n;
    a[1]=1;
    long long int suma=0;
    while(n>=10)
    {
        int t=0;
        for(int j=1; j<=c; j++)
        {
            int cif=a[j]*1024+t;
            a[j] = cif % 10;
            t=cif/10;
        }
        while(t)
        {
            a[++c]=t%10;
            t/=10;
        }
        n-=10;
    }
    
    while(n)
    {
        int t=0;
        for(int j=1; j<=c; j++)
        {
            int cif=a[j]*2+t;
            a[j] = cif % 10;
            t=cif/10;
        }
        while(t)
        {
            a[++c]=t%10;
            t/=10;
        }
        n--;
    }
    for(int i = 1 ; i <= c ; ++i)
        suma+=a[i];
    cout << suma;
    return 0;
}