Cod sursa(job #465077)

Utilizator gcosminGheorghe Cosmin gcosmin Data 23 iunie 2010 11:36:04
Problema Prod Scor Ascuns
Compilator cpp Status done
Runda Marime 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;
}