Cerința

Se dă o mulţime A formată din n elemente, numere naturale ( evident distincte ). Aflaţi câte submulţimi nevide ale lui A au suma elementelor număr par.

Date de intrare

Fișierul de intrare memory005.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale distincte, separate prin spații, reprezentând elementele mulţimii A.

Date de ieșire

Fișierul de ieșire memory005.out va conține pe prima linie numărul S, reprezentând numărul submulţimilor nevide ale lui A care au suma elementelor număr par. Rezultatul se va afişa modulo 666013.

Restricții și precizări

1 ≤ n ≤ 1.000.000
numerele de pe a doua linie a fișierului de intrare vor fi distincte şi mai mici decât 2.000.000.000

Exemplu

memory005.in

4
1 3 8 2

memory005.out

Explicație

Avem mulţimea A={1,3,8,2}. Submulţimile nevide ale lui A având suma elementelor număr par sunt: {8}, {2}, {1,3}, {8,2}, {1,3,8}, {1,3,2}, {1,3,8,2}.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Memory005:

#include <fstream>

using namespace std;
ifstream f("memory005.in");
ofstream g("memory005.out");
long long n , i , j , p , x , m , a[30] ;

int main()
{
    f >> n ;
    // verific daca multimea are un element impar
    f >> x ;
    i = 1 ;
    while ( (i<n) and (x%2==0) ) { f >> x ; i++ ; }
    m = n - x%2 ;
    // trec m in baza 2 pentru a calcula 2^m in timp logaritmic
    j = 0 ;
    while ( m!=0 )
    {
       j++ ;
       a[j] = m%2 ;
       m = m/2 ;
    }
    // calculez 2^m in timp logaritmic
    p = 1 ;
    for ( i=j ; i>=1 ; i--)
    {
        if ( a[i]==1 ) p =( p * p * 2 ) % 666013 ;
                  else p = ( p * p ) % 666013 ;
    }
    p = ( p -1 ) % 666013 ;
    g << p ;
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1834 Memory005

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1834 Memory005 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1834 Memory005