Cod sursa(job #474027)

Utilizator daniel.dumitranDaniel Dumitran daniel.dumitran Data 2 august 2010 01:52:12
Problema Pascal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <stdio.h>

struct desc {
  int f2, f3, f5;
};

#define LIMIT 1000000

int cache[6][LIMIT];

void calc_cache(int x) {
  cache[x][0] = 0;
  for (int i = 0; i < LIMIT; ++i) {
    int rest = i / x;
    cache[x][i] = rest + cache[x][rest];
  }
}

void init_cache() {
  calc_cache(2);
  calc_cache(3);
  calc_cache(5);
}

int get_exp(int nr, int div) {
  int rez = 0;
  while (nr >= LIMIT) {
    nr /= div;
    rez += nr;
  }
  rez += cache[div][nr];
}

void get_desc(desc* d, int x) {
  d->f2 = get_exp(x, 2);
  d->f3 = get_exp(x, 3);
  d->f5 = get_exp(x, 5);
}

void mul_desc(desc* a, desc* b) {
  a->f2 += b->f2;
  a->f3 += b->f3;
  a->f5 += b->f5;
}

void div_desc(desc* a, desc* b) {
  a->f2 -= b->f2;
  a->f3 -= b->f3;
  a->f5 -= b->f5;
}

bool is_disibile(desc* a, desc *b) {
  return (a->f2 >= b->f2) && (a->f3 >= b->f3) && (a->f5 >= b->f5);
}

int main() {
  int r, d;
  FILE *f = fopen("pascal.in", "rt");
  fscanf(f, "%d %d", &r, &d);
  fclose(f);

  init_cache();

  desc dd; get_desc(&dd, d);
  int rez = 0;
  int i = r;
  desc old; get_desc(&old, 0);
  for (int j = 1; j <= r / 2; ++j) {
    desc mul; get_desc(&mul, i - j);
    desc imp; get_desc(&imp, j);
    mul_desc(&old, &mul);
    div_desc(&old, &imp);
    if (is_disibile(&old, &dd)) {
      ++rez;
      if (j < r / 2) ++rez;
    }
  }

  f = fopen("pascal.out", "wt");
  fprintf(f, "%d\n", rez);
  fclose(f);
  
  return 0;
}