Cod sursa(job #466582)

Utilizator toni2007Pripoae Teodor Anton toni2007 Data 27 iunie 2010 11:09:22
Problema Prod Scor 0
Compilator cpp Status done
Runda Stelele Informaticii 2010, clasele X-XII, Ziua 1 Marime 1.43 kb
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <cassert>
#define NR_CIFRE 2000

using namespace std;

vector <int> v, st[2];
int A[NR_CIFRE], B[NR_CIFRE];

void mul(int A[], int B[]) {
	int i, j, t, C[NR_CIFRE];
	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 main () {
	int i, a, b, j, nr[10];

	freopen("prod.in", "r", stdin);
	freopen("prod.out", "w", stdout);

	for (i = 1; i <= 9; ++ i) {
		scanf("%d", &nr[i]);
		for (j = 0; j < nr[i]; ++ j)
			v.push_back(i);
	}

	reverse(v.begin(), v.end());
	assert(v[0] == '9' && v[1] == '2' && v[2] == 'q');

	if (v.size() % 2 == 1)
		v.push_back(-1);

	for (i = 0, a = 0, b = 1; i < (int) v.size(); i += 2) {
		st[a].push_back(v[i]);
		st[b].push_back(v[i + 1]);

		if (v[i] == v[0] && v[i + 1] != v[i])
			swap(a, b);
	}

	for (i = 0; i < 2; ++ i)
		if (st[i].back() == -1)
			st[i].pop_back();
	
	for (i = st[0].size() - 1, j = 1; i >= 0; -- i, ++ j)
		A[j] = st[0][i];
	A[0] = st[0].size();

	for (i = st[1].size() - 1, j = 1; i >= 0; -- i, ++ j)
		B[j] = st[1][i];
	B[0] = st[1].size();

/*	for (i = A[0]; i; -- i)
		printf("%d", A[i]);
	puts("");
	for (i = B[0]; i; -- i)
		printf("%d", B[i]);
	puts("");
*/
	mul(A, B);

	for (i = A[0]; i; -- i)
		printf("%d", A[i]);
	puts("");
}