Cod sursa(job #1216883)

Utilizator daniel.dumitranDaniel Dumitran daniel.dumitran Data 6 august 2014 00:00:19
Problema Pascal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <stdio.h>
 
struct desc {
  int f2, f3, f5;
};
 
#define LIMIT 5000001

int exp2[LIMIT], exp3[LIMIT], exp5[LIMIT];
 
void get_desc(desc* d, int x) {
  d->f2 = exp2[x];
  d->f3 = exp3[x];
  d->f5 = exp5[x];
}
 
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);

  exp2[0] = exp3[0] = exp5[0] = 0;
  for (int i = 1; i <= r || i <= d; ++i) {
    exp2[i] = i % 2 ? 0 : 1 + exp2[i / 2];
    exp3[i] = i % 3 ? 0 : 1 + exp3[i / 3];
    exp5[i] = i % 5 ? 0 : 1 + exp5[i / 5];
  }
 
  desc dd; get_desc(&dd, d);
  int rez = 0;
  int i = r;
  desc old; get_desc(&old, 0);
  for (int j = 1; j * 2 <= r; ++j) {    
    desc mul; get_desc(&mul, i - j + 1);
    desc imp; get_desc(&imp, j);
    mul_desc(&old, &mul);
    div_desc(&old, &imp);
    if (is_disibile(&old, &dd)) {
      ++rez;
      if (j * 2 < r) ++rez;      
    }
  }
 
  f = fopen("pascal.out", "wt");
  fprintf(f, "%d\n", rez);
  fclose(f);
   
  return 0;
}