Cod sursa(job #465593)

Utilizator wefgefAndrei Grigorean wefgef Data 24 iunie 2010 21:04:14
Problema Prod Scor Ascuns
Compilator cpp Status done
Runda Marime 1.48 kb
#include <cassert>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAX_DIGITS = 1024;

int digit[10];
int a[MAX_DIGITS], b[MAX_DIGITS];
int n;

int nextDigit() {
    static int p = 9;

    while (p > 0 && digit[p] == 0)
        --p;
    assert(p > 0);

    --digit[p];
    return p;
}

void reverse(int a[]) {
    int p = 1, q = a[0];
    while (p < q) {
        swap(a[p], a[q]);
        ++p, --q;
    }
}


void multiply(int A[], int B[]) {
    int i, j, t, C[MAX_DIGITS];
    memset(C, 0, sizeof(C));
    for (i = 1; i <= A[0]; i++) {
        for (t=0, j=1; j <= B[0] || t; j++, t/=10)
            C[i+j-1]=(t+=C[i+j-1]+A[i]*B[j])%10;
        if (i + j - 2 > C[0]) C[0] = i + j - 2;
    }
    memcpy(A, C, sizeof(C));
}

int addDigit(int a[]) {
    --n;
    return a[++a[0]] = nextDigit();
}

int main() {
    assert(freopen("prod.in", "r", stdin) != NULL);
    assert(freopen("prod.out", "w", stdout) != NULL);

    for (int i = 1; i < 10; ++i)
        assert(scanf("%d", &digit[i]) == 1);

    for (int i = 1; i < 10; ++i)
        n += digit[i];

    bool equal = true;
    if (n & 1) {
        addDigit(a);
        equal = false;
    }
    while (n) {
        if (equal) {
            if (addDigit(a) != addDigit(b))
                equal = false;
        } else {
            addDigit(b);
            addDigit(a);
        }
    }
    reverse(a);
    reverse(b);

    multiply(a, b);

    for (int i = a[0]; i > 0; --i)
        printf("%d", a[i]);
    printf("\n");
}