Cod sursa(job #2224221)

Utilizator andrei.arnautuAndi Arnautu andrei.arnautu Data 23 iulie 2018 14:40:55
Problema Bile2 Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.37 kb
/**
  *  Worg
  */
#include <cstdio>
#include <cstring>
#include <algorithm>

FILE *fin = freopen("bile2.in", "r", stdin); FILE *fout = freopen("bile2.out", "w", stdout);

const int MAX_N = 1000 + 5;
const int MAX_SIZE = 60;
const int BASE = 1e9;
const int BASE_DIGITS = 9;

class Huge {
  public:

    int a[MAX_SIZE];
    int size;

    void Reset() {
      memset(a, 0, sizeof(a));
      size = 1;
    }
    
    Huge() {
      Reset();
    }

    void SetValue(long long value) {
      Reset();

      do {
        a[++size] = value % BASE;
        value /= BASE;
      }while(value != 0);
    }

    void operator = (const Huge &other) {
      this->size = other.size;
      for(int i = 1; i < MAX_SIZE; i++) {
        this->a[i] = other.a[i];
      }
    }

    void operator *= (long long value) {
      long long i, t;
      for(i = 1, t = 0; i <= size || t != 0; i++, t /= BASE) {
        a[i] = (t += a[i] * value) % BASE;
      }
    }

    void operator /= (long long value) {
      long long i, t;
      for(i = size, t = 0; i > 0; i--) {
        t = t * BASE + a[i];
        a[i] = t / value;
        t %= value; 
      }

      while(size > 1 && a[size] == 0) {
        size--;
      }
    }

    void operator += (const Huge &other)  {
      int i, j, t;
      for(i = 1, j = 1, t = 0; i <= this->size || j <= other.size || t != 0; i++, j++, t /= BASE) {
        t += this->a[i] + other.a[i];
        this->a[i] = t % BASE;
      }

      this->size = i - 1;
    }

    void operator -= (const Huge &other) {
      int i, t;
      for(i = 1; i <= this->size; i++) {
        this->a[i] -= (other.a[i] + t);
        t = 0;

        if(this->a[i] < 0) {
          this->a[i] += BASE;
          t = 1;
        }
      }

      while(this->size > 1 && this->a[this->size] == 0) {
        this->size--;
      }
    }

    Huge operator *(const Huge &other) {
      Huge answer;

      for(int i = 1; i <= this->size; i++) {
        long long t = 0;

        int j;
        for(j = 1; j <= other.size || t; j++, t /= BASE) {
          t += answer.a[i + j - 1] + 1LL * this->a[i] * other.a[j];
          answer.a[i + j - 1] = t % BASE;
        }

        answer.size = std::max(answer.size, i + j - 2);
      }

      return answer;
    }

    bool operator >(const Huge &other) const {
      if(this->size != other.size) {
        return this->size > other.size;
      }

      for(int i = this->size; i > 0; i--) {
        if(this->a[i] != other.a[i]) {
          return this->a[i] > other.a[i];
        }
      }

      return false;
    }
};

/*-------- Data --------*/
Huge comb, a, b;
Huge dp[2][MAX_N];
/*-------- --------*/

bool Check(Huge _a, Huge _b, Huge _c, Huge _d) {
  Huge x = _a * _d;
  Huge y = _b * _c;

  return y > x;
}

int main() {
  long long n, d, frac_a, frac_b; scanf("%lld%lld%lld%lld", &n, &d, &frac_a, &frac_b);

  frac_a = frac_b - frac_a;

  a.SetValue(frac_a); b.SetValue(frac_b); comb.SetValue(n);
  for(int i = 1; i <= n; i++) {
    dp[0][i].SetValue(i);
  }

  int now = 1, before = 0;
  int level = 1;

  while(Check(a, b, dp[before][n], comb)) {
    comb *= (n - level);
    level++;
    comb /= level;

    dp[now][level - 1].SetValue(0); dp[now][level - 1].SetValue(0);

    for(int i = level; i <= n; i++) {
      dp[now][i] = dp[now][i - 1];

      if(i - d - 1 > 0) {
        dp[now][i] += dp[before][i - d - 1];
      }
    }

    now ^= 1; before ^= 1;
  }

  printf("%d\n", level);
  return 0;
}