Question

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

Answer 1

#include <iostream>

using namespace std;

int n , m , i , s , j , a[100000] , t , x ;

int main()

{

   cin >> n ;

   a[1] = 1 ; ///calculam suma cifrelor lui 2^n (toate comb posibile de 3 si 4)

   m = 1 ;

   for ( i = 1 ; i <= n ; i++ )

     {

       t = 0 ;  ///depaseste 10000?, poate fi 0 sau 1

       for ( j = 1 ; j <= m ; j++ )  /// m = cate grupari de 4 cifre are nr final

         {

             x = a[j] ;     ///retin in a[j] cate 4 cifre din numar

             a[j] = ( a[j] * 2 + t ) % 10000 ;

             t = ( x * 2 + t ) / 10000 ;

           ///  cout<<a[j]<<'\t'<<t<<'\n';

         }

       if ( t > 0 ) { m++ ; a[m] = t ;}

     }

    s = 0 ;

    /// cout<<"#"<<m<<'\n';

    for ( i = 1 ; i <= m ; i++ )

    {

     ///   cout<<a[i]<<" ";

        x = a[i] ;

        while ( x != 0)

         {

             s = s + x % 10 ;

             x = x / 10 ;

         }

    }

    cout << s ;

   return 0;

}