# Cod sursa(job #465077)

Utilizator Data 23 iunie 2010 11:36:04 Prod Ascuns cpp done 3.77 kb
``````#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;

#define CMAX 1000010

#define FIN "prod.in"
#define FOUT "prod.out"

int nr[20];

int rez_greedy[CMAX], rez_back[CMAX];

int a[CMAX], b[CMAX];

int C[CMAX];
void mul(int A[], int B[])
{
int i, j, t;
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 mai_mic(int a[], int b[])
{
if (a[0] < b[0]) return 1;
if (a[0] > b[0]) return 0;

for (int i = a[0]; i >= 1; i--) {
if (a[i] < b[i]) return 1;
if (a[i] > b[i]) return 0;
}

return 0;
}

int egal(int a[], int b[])
{
if (a[0] != b[0]) return 0;

for (int i = a[0]; i >= 1; i--) {
if (a[i] != b[i]) return 0;
}

return 1;
}

void reverse_nr(int a[])
{
int i, j;

for (i = 1, j = a[0]; i <= j; i++, j--)
swap(a[i], a[j]);
}

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

void solve_greedy()
{
FILE *f = fopen(FIN, "r");

int i, j;
vector <int> c;

for (i = 1; i <= 9; i++) {
fscanf(f, "%d", &nr[i]);
}

for (i = 9; i >= 1; i--) {
for (j = 1; j <= nr[i]; j++)
c.push_back(i);
}

int e = 0;
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));

/*	if (c.size() % 2) { // nr impar de cifre
a[++a[0]] = c[0];
e = 1;
}
*/
for (i = 0; i + 1 < (int)c.size(); i += 2) {
int c1 = c[i], c2 = c[i + 1];

if (c1 == c2) a[++a[0]] = c1, b[++b[0]] = c2;
else {
if (e) a[++a[0]] = min(c1, c2), b[++b[0]] = max(c1, c2);
else {
a[++a[0]] = max(c1, c2); b[++b[0]] = min(c1, c2);
e = 1;
}
}
}

if (c.size() % 2) b[++b[0]] = c[c.size() - 1];

reverse_nr(a);
reverse_nr(b);

//print_nr(a);
//print_nr(b);

mul(a, b);

fclose(f);

f = fopen(FOUT, "w");

for (i = a[0]; i >= 1; i--) fprintf(f, "%d", a[i]);
fprintf(f, "\n");

fclose(f);

memcpy(rez_greedy, a, sizeof(rez_greedy));
}

void solve_back()
{
FILE *f = fopen("prod.in", "r");

int i, j, k;
vector <int> c;

for (i = 1; i <= 9; i++) {
fscanf(f, "%d", &nr[i]);
}

for (i = 1; i <= 9; i++) {
for (j = 1; j <= nr[i]; j++)
c.push_back(i);
}

int n = c.size();
int rez[CMAX];
memset(rez, 0, sizeof(rez));

char nrb[1 << n];
nrb[0] = 0;

for (i = 1; i < (1 << n); i++) {
nrb[i] = nrb[i >> 1] + (i & 1);
if (abs((n - nrb[i]) - nrb[i]) > 1) continue;
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));

for (j = 1, k = 0; j < (1 << n); j <<= 1, k++)
if (j & i) a[++a[0]] = c[k];
else b[++b[0]] = c[k];

mul(a, b);

if (mai_mic(rez, a)) memcpy(rez, a, sizeof(a));
}

fclose(f);

f = fopen("prod.out", "w");

for (i = rez[0]; i >= 1; i--) fprintf(f, "%d", rez[i]);
fprintf(f, "\n");

fclose(f);

memcpy(rez_back, rez, sizeof(rez_back));
}

int gen(int N)
{
FILE *f = fopen("prod.in", "w");

memset(nr, 0, sizeof(nr));

int i;

for (i = 1; i <= N; i++) {
int c = rand() % 9 + 1;
nr[c]++;
}

for (i = 1; i <= 9; i++) fprintf(f, "%d ", nr[i]);
fprintf(f, "\n");

fclose(f);

return 0;
}

int main()
{
/*for (int i = 1; i <= 1000; i++) {
int N = rand() % 19 + 2;

gen(N);

//for (int j = 1; j <= 9; j++) printf("%d ", nr[j]);
//printf("\n");

solve_greedy();
solve_back();

if (!egal(rez_greedy, rez_back)) {
printf("jeeeeeeeeeeeeeeg\n");
print_nr(rez_back);
print_nr(rez_greedy);
return 0;
} else {
printf("%d - OK!!! -> ", i);
print_nr(rez_greedy);
}
}*/

solve_back();

return 0;
}
``````