Cod sursa(job #1845126)

Utilizator bobotheslayerBogdan Zaharia bobotheslayer Data 10 ianuarie 2017 22:17:51
Problema Ridicare la putere in timp logaritmic Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
// http://www.infoarena.ro/problema/fact
// Se da un numar intreg P. Sa se gaseasca cel mai mic numar natural strict pozitiv N pentru care N! are exact P cifre de 0 la sfarsit.

#include<cstdio>

// functia zerouri este crescatoare
int zerouri(int n)
{
  int num=0;
  while (n>0)
  {
    num=num+n/5;
    n=n/5;
  }
  return num;
}

int main() {
  FILE *intrare, *iesire;
  intrare=fopen("fact.in","r");
  iesire=fopen("fact.out","w");
  
  int p;
  fscanf(intrare,"%d",&p);
  
  int st=0,dr=1000000000;
  while (st<dr)
  {
    int mijloc=(st+dr)/2;
    int num=zerouri(mijloc);
    if (num<p)
    {
      st=mijloc+1;
    }
    else if (num>=p)
    {
      dr=mijloc-1;
    }
  }
  if (zerouri(st)==p)
  {
    fprintf(iesire,"%d",st);
  }
  else
  {
    fprintf(iesire,"-1");
  }
  
  /*
  for (int i=1; i<=10000000000; ++i) {
    if (zerouri(i)==p) {
      fprintf(iesire,"%d",i);
      return 0;
    }
  }
  */
  
  fclose(intrare);
  fclose(iesire);
}