Cod sursa(job #731878)

Utilizator danalex97Dan H Alexandru danalex97 Data 9 aprilie 2012 12:56:47
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];

inline 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;
}