Cod sursa(job #1691713)

Utilizator sucureiSucureiRobert sucurei Data 19 aprilie 2016 11:43:08
Problema Pavare2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.42 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;
}