Cod sursa(job #743045)

Utilizator mihai995mihai995 mihai995 Data 2 mai 2012 22:27:30
Problema Bile2 Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.84 kb
#include <fstream>
#include <cstring>
using namespace std;

const int N = 1005, LMax = 64;

ifstream in("bile2.in");
ofstream out("bile2.out");

struct Mare
{
    short int mare[LMax];

    void sloppy()
    {
        int i;

        for (i = 1 ; i <= mare[0] || mare[i] ; i++)
            if (mare[i] > 9)
            {
                mare[i + 1] += mare[i] / 10;
                mare[i] %= 10;
            }

        mare[0] = i > 1 ? i - 1 : 1;
    }

    void get()
    {
        char s[LMax];

        in >> s;

        mare[0] = strlen(s);

        for (int i = mare[0] , j = 0 ; s[j] ; j++, i--)
            mare[i] = s[j] - '0';
    }

    void operator= (int x)
    {
        memset(mare, 0, sizeof(mare));
        mare[1] = x;
        sloppy();
    }

    Mare operator+ (Mare& Num)
    {
        Mare rez; rez = 0;
        short int *v = rez.mare, *a = mare, *b = Num.mare;
        int i, t = 0;

        for (i = 1 ; i <= a[0] || i <= b[0] || t; i++, t /= 10)
            v[i] = (t += a[i] + b[i]) % 10;

        v[0] = i - 1;

        return rez;
    }

    Mare operator- (Mare& Num)
    {
        Mare rez; rez = *this;
        short int *a = rez.mare, *b = Num.mare;
        int i, t=0;

        for (i = 1 ; i <= a[0] ; i++)
        {
            a[i] -= b[i];

            if (a[i] < 0)
            {
                a[i] += 10;
                a[i + 1]--;
            }
        }

        for ( ; !a[a[0]] ; a[0]--);

        return rez;
    }

    Mare operator* (Mare& Num)
    {
        Mare rez; rez = 0;

        short int *v = rez.mare, *a = mare, *b = Num.mare;

        v[0] = a[0] + b[0] - 1;

        for (int i = 1 ; i <= a[0] ; i++)
            for (int j = 1 ; j <= b[0] ; j++)
                v[i + j - 1] += a[i] * b[j];

        rez.sloppy();
        return rez;
    }

    bool operator<= (Mare Num)
    {
        short int *a = mare, *b = Num.mare;

        if (a[0] != b[0])
            return a[0] < b[0];

        for (int i = a[0] ; i ; i--)
            if (a[i] != b[i])
                return a[i] < b[i];

        return true;
    }

} v[N][N], comb[N][N];

int main()
{
    int n, D;
    Mare A, B;

    in >> n >> D; D++;

    A.get();
    B.get();

    for (int i = 1 ; i <= n ; i++)
        v[1][i] = i;

    for (int i = 1 ; i <= n ; i++)
    {
        comb[i][0] = 1;
        comb[i][i] = 1;

        for (int j = 1 ; j < i ; j++)
            comb[i][j] = comb[i - 1][j] + comb[i - 1][j - 1];
    }

    for (int i = 2 ; i <= n ; i++)
    {
        for (int j = D + 1 ; j <= n ; j++)
            v[i][j] = v[i][j - 1] + v[i - 1][j - D];

        if ((A * comb[n][i])<= ((comb[n][i] - v[i][n]) * B))
        {
            out << i << "\n";
            return 0;
        }
    }
    out << "-1\n";
    return 0;
}