Cod sursa(job #1131516)

Utilizator otto1Palaga Vicentiu-Octavian otto1 Data 28 februarie 2014 20:58:40
Problema Pavare2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.87 kb
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#define MAXN 110
#define MAXL 110

using namespace std;

int A, B, n;
char c;
int din[MAXN][MAXN][2][MAXL], tmp[MAXL], k[MAXL], tmp2[MAXL];

void atrib0(int *h)
{
	h[0] = 0;
}

void atribValue(int *h, int x)
{
	h[0] = 0;
	while (x)
	{
		++h[0];
		h[h[0]] = x % 10;
		x /= 10;
	}
}

void atribHuge(int *dst, int *src)
{
	for (int i = 0; i <= src[0]; ++i)
		dst[i] = src[i];
}

void addHuge(int *a, int *b)
{
	int i, T = 0;

	if (b[0] > a[0])
	{
		for (i = a[0] + 1; i <= b[0];) a[i++] = 0;
		a[0] = b[0];
	}
	else
		for (i = b[0] + 1; i <= a[0];) b[i++] = 0;
	for (i = 1; i <= a[0]; ++i)
	{
		a[i] += b[i] + T;
		T = a[i] / 10;
		a[i] %= 10;
	}
	if (T) a[++a[0]] = T;
}

void printHuge(int *a)
{
	for (int i = a[0]; i > 0; --i)
		printf("%d", a[i]);
	puts("");
}

int cmpHuge(int* H1, int *H2)
{
	while (H1[0] && !H1[H1[0]]) H1[0]--;
	while (H2[0] && !H2[H2[0]]) H2[0]--;

	if (H1[0] < H2[0]) {
	return -1;
	} else if (H1[0] > H2[0]) {
	return +1;
	}

	for (int i = H1[0]; i > 0; --i) {
	if (H1[i] < H2[i]) {
	  return -1;
	} else if (H1[i] > H2[i]) {
	  return +1;
	}
	}
	return 0;
}

void subHuge(int *A, int *B)
{
	int i, T=0;

	for (i=B[0]+1;i<=A[0];) B[i++]=0;
	for (i=1;i<=A[0];i++)
	A[i]+= (T=(A[i]-=B[i]+T)<0) ? 10 : 0;
	while (!A[A[0]]) A[0]--;
}


int main()
{
	freopen("pavare2.in", "r", stdin);
	freopen("pavare2.out", "w", stdout);
	scanf("%d %d %d\n", &n, &A, &B);

	while (isdigit(c = getchar()))
		k[++k[0]] = c - '0';

	for (int i = 1; i <= k[0] >> 1; ++i)
	{
		int aux = k[i];
		k[i] = k[k[0] - i + 1];
		k[k[0] - i + 1] = aux;
	}

	atribValue(din[1][1][0], 1);
	atribValue(din[1][1][1], 1);
	atribValue(din[1][105][0], 1);
	atribValue(din[1][105][1], 1);
	atribValue(din[0][105][0], 1);
	atribValue(din[0][105][1], 1);

	for (int lev = 2; lev <= n; ++lev)
	{
		for (int i = 1; (i - lev - 1) && (i - A - 1); ++i)
		{
			atribHuge(din[lev][i][0], din[lev - i][105][1]);
			addHuge(din[lev][105][0], din[lev][i][0]);
		}
		for (int i = 1; (i - lev - 1) && (i - B - 1); ++i)
		{
			atribHuge(din[lev][i][1], din[lev - i][105][0]);
			addHuge(din[lev][105][1], din[lev][i][1]);
		}
	}

	atribHuge(tmp, din[n][105][0]);
	addHuge(tmp, din[n][105][1]);
	printHuge(tmp);

	int left = n;
	while (left > 0)
	{
		int found = 0;
		atrib0(tmp);
		for (int i = left; i > 0; --i)
		{
			atribHuge(tmp2, tmp);
			addHuge(tmp2, din[left][i][0]);
			if (cmpHuge(tmp2, k) >= 0)
			{
				found = i;
				break;
			}
			atribHuge(tmp, tmp2);
		}
		if (found)
		{
			subHuge(k, tmp);
			for (int i = 0; i < found; ++i)
				printf("0");
			if (left != found)
				printf("1");
			left -= found + 1;
			continue;
		}
		printf("1");
		subHuge(k, din[left][105][0]);
		--left;
	}
	puts("");
	return 0;
}