Cod sursa(job #1541908)

Utilizator sulzandreiandrei sulzandrei Data 4 decembrie 2015 17:59:26
Problema Factorial Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("fact.in");
ofstream out("fact.out");
#define nw10to8z 1000000
long long  fives[nw10to8z],twos[nw10to8z];
int five(int i)
{
    int nr= 0;
    while(i>=5)
    {
        if (i % 5 == 0)
            nr++,i/=5;
        else
            i = 4;
    }
    return nr;
}
int main()
{
    int  n,lo,hi,p,mij;
    in>> p;
    twos[ 1] = fives[ 1] = 0;
    for(int i = 1 ; i <= nw10to8z; i++)
    {
        if (i % 5 == 0)
            fives[i] = fives[i-5] +five(i);
        else
            fives[i] = fives[i-1];
    }
    //for(int i = 1000000 ; i<= nw10to8z && fives[i]!=-1; i ++)
      //  cout<<fives[i]<<" "<<i<<"\n";
    lo =  1,hi = nw10to8z;
    p;
    in>>p;
    while ( hi - lo >1)              //ne trebuie cea mai mica pozitie pentru care min(fives[mij],twos[mij])>=p, daca exista
    {
        mij = lo +(hi-lo )/2 ;
        if( fives[mij] >= p)
            hi = mij;
        else
            lo = mij+1;
    }
    if( fives[lo] >= p)
    {
        out<<lo;
        return 0;
    }
    if ( fives[hi] >= p)
    {
        out<<hi;
        return 0;
    }
    out<<"-1";
    return 0;
}