X şi Y se joacă cu N biluţe, fiecare biluţă având scrisă pe ea o cifră nenulă. Inventivi din fire, aceştia au împărţit cele N biluţe în două grămezi, astfel încât valoarea medie a grămezii lui X să fie egală cu valoarea medie a grămezii lui Y. Valoarea medie a unei grămezi este egală cu suma tuturor numerelor din grămadă împărţită la numărul de elemente ale acesteia.

Cerința

Dându-se cele N valori scrise pe biluţe, aflaţi în câte moduri pot fi împărţite biluţele în două grămezi ale căror valori medii să fie egale. Cum acest număr poate fi prea mare, afişaţi doar restul împărţirii acestui număr la 666013.

Date de intrare

Fișierul de intrare bilute1.in conține pe prima linie numărul natural N, iar pe a 2-a linie se afla N numere naturale separate prin exact un spaţiu, reprezentând valorile scrise pe cele N biluţe.

Date de ieșire

Fișierul de ieșire bilute1.out va conține un singur număr, reprezentând numărul de moduri în care pot fi împărţite biluţele în grămezi, conform cerinţei de mai sus.

Restricții și precizări

2 ≤ N ≤ 750
Două configuraţii sunt considerate distincte dacă există cel puţin o biluţă care se află în grămezi diferite
Pentru o configuraţie, ordinea de repartizare a grămezilor pentru X şi Y este semnificativă
Fiecare grămadă trebuie să conţină cel puţin o biluţă
Fiecare biluţă trebuie să se afle în exact una dintre cele două grămezi
Pentru 15% dintre teste N ≤ 20
Pentru 25% dintre teste valoarea de pe biluţe ≤ 3

Exemplul 1

bilute1.in

6
1 2 3 4 5 6

bilute1.out

Explicație

GX=[1,2,5,6]; GY=[3,4], unde (1+2+5+6)/4=(3+4)/2
GX=[1,3,4,6]; GY=[2,5]
GX=[1,6]; GY=[2,3,4,5]
GX=[2,3,4,5]; GY=[1,6]
GX=[2,5]; GY=[1,3,4,6]
GX=[3,4]; GY=[1,2,5,6]

Exemplu

bilute1.in

6
1 1 2 2 3 3

bilute1.out

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 Bilute1:

#define TuTTy "Cosmin-Mihai Tutunaru"
#include <cstdio>
#include <vector>
#include <algorithm>
#define infile "bilute1.in"
#define outfile "bilute1.out"
#define vMax 13
#define nMax 1013
#define sMax 10013
#define modulo 666013
#define ll long long

using namespace std;

int dp[nMax][sMax];
int v[nMax];
int n, s, sol;

bool usedSums[nMax][sMax];
vector <int> sums[nMax];

void read() {
    scanf("%d\n", &n);
    for (int i = 1; i < n+1; ++i) {
        scanf("%d", &v[i]);
        s += v[i];
    }
}

void solve() {
    dp[0][0] = 1;
    int crtSum = 0;

    sums[0].push_back(0);
    sort(v+1, v+n+1);

    for (int k = 1; k < n+1; ++k) {
        crtSum += v[k];

        for (int i = min(n/2 + 1, k); i > 0; --i) {
            for (size_t j = 0; j < sums[i-1].size(); ++j) {
                int val = sums[i-1][j] + v[k];

                if (val > crtSum) {
                    continue;
                }

                dp[i][val] += dp[i-1][sums[i-1][j]];
                if (dp[i][val] >= modulo) {
                    dp[i][val] -= modulo;
                }

                if (val <= s/2 + 1 && !usedSums[i][val]) {
                    usedSums[i][val] = true;
                    sums[i].push_back(val);
                }
            }
        }
    }

    for (int i = 1; i < n+1; ++i) {
        for (int j = 1; j < s+1; ++j) {
            if (i != n && j * n == s * i) {
                sol += dp[min(i, n-i)][min(j, s-j)];
                sol %= modulo;
            }
        }
    }
}

void write() {
    printf("%d\n", sol % modulo);
}

int main() {
    freopen(infile, "r", stdin);
    freopen(outfile, "w", stdout);

    read();
    solve();
    write();

    fclose(stdin);
    fclose(stdout);
    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 #1644 Bilute1

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1644 Bilute1 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 #1644 Bilute1