👤
ANDREEA1104EN
a fost răspuns

Am nevoie de ajutor la aceasta problema.Multumesc!
Pentru mai multe multimi de numere naturale consecutive de la 1 la n, se pot imparti in 2 submultimi(a caror intersectie este multimea vida si reuniune multimea nr nat de la 1 la n) care sa aiba suma elementelor egala.
De exemplu daca n=3, multimea este {1,2,3}, iar singura varianta pentru cele 2 submultimi ar fi {1,2} si {3}. Se considera valida numai aceasta varianta, nu si {3} cu {1,2}, deoarece acestea sunt identice.
Faceti un program care sa calculeze numarul de moduri distincte in care poate fi impartita multimea astfel incat suma elementelor din fiecare multime sa fie egala. Daca nu se poate realiza nicio varianta corecta se va afisa valoarea 0;
Fisierul de intrare semisume.in conţine o singură linie, cu un singur număr întreg n.
Fisierul de iesire semisume.out contine tot o singura linie unde se va afisa raspunsul la cerinta.
Restricţii
1<=n<=39;

Răspuns :

PLOPLO123EN

Răspuns:

#include <iostream>

#include <fstream>

using namespace std;

const int NMAX = 40;

unsigned int dp[NMAX * ( NMAX + 1 ) / 2 / 2 + 1][NMAX];

int main() {

   ifstream fin( "semisume.in" );

   ofstream fout( "semisume.out" );

   int n, i, s, j;

   fin >> n;

   s = n * ( n + 1 ) / 2;

   if ( s % 2 == 1 )

       fout << 0 << endl;

   else {

       for ( i = 0; i <= n; i ++ ) {

           dp[0][i] = 1;

       }

       for ( i = 1; i <= s / 2; i ++ ) {

           for ( j = 1; j <= n; j ++ ) {

               dp[i][j] = dp[i][j - 1];

               if ( i - j >= 0 )

                   dp[i][j] += dp[i - j][j - 1];

           }

       }

       fout << dp[s / 2][n] / 2 << '\n';

   }

   return 0;

}

Explicație:

TIBERIU02EN

# include <iostream>

# include <fstream>

# include <cmath>

using namespace std;

const int MAX_S = 1600;

long long d[2][MAX_S * 2];

int main() {

   ifstream fin( "semisume.in" );

   ofstream fout( "semisume.out" );

   int n;

   fin >> n;

   d[0][0] = 1;

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

       for ( int k = 0; k < MAX_S; k ++ )

           d[i & 1][k] = d[i & 1 ^ 1][k + i] + d[i & 1 ^ 1][(int)abs( k - i )];

   fout << d[n & 1][0] / 2;

   return 0;

}

Vă mulțumim că ați vizitat site-ul nostru dedicat Informatică. Sperăm că informațiile oferite v-au fost de ajutor. Dacă aveți întrebări sau nevoie de asistență suplimentară, nu ezitați să ne contactați. Vă așteptăm cu drag data viitoare și nu uitați să ne adăugați la favorite!


En Learnings: Alte intrebari