Pagini recente » Cod sursa (job #2954449) | Cod sursa (job #3818) | Profil alexdinu712 | Cod sursa (job #1319946) | Cod sursa (job #448372)
Cod sursa(job #448372)
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#define MAXN 110
using namespace std;
int A, B, n;
char c;
int din[MAXN][MAXN][2][MAXN], tmp[MAXN], k[MAXN], tmp2[MAXN];
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[i] = 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;
}