Cod sursa(job #758143)

Utilizator bratualexBratu Alexandru bratualex Data 14 iunie 2012 16:29:57
Problema Factorial Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <fstream>

using namespace std;
ifstream fin ( "fact.in");
ofstream fout ("fact.out");

long cauta(long,long,long );
long nrzero (long);
long pt[14];
int main()
{
    long n,m,i=0;
    fin>>n;
    pt[1]=5;
    pt[0]=1;
    for ( i=1;i<13;i++)
        pt[i+1]=pt[i]*5;

    m=n*5;
    if ( n==0 )
        fout<<1;
    else
    {
        m=cauta(1,m,n);
        while ( m%5 )
            m--;

        fout<<m;
    }


    fin.close();
    fout.close();
    return 0;

}

long cauta (long a, long b , long nrz )
{
    long aux;
    //fout<<"cauta primeste "<<a<<" "<<b<<" "<<" "<<nrz<<"\n";
    aux=nrzero((a+b)/2);
    if ( nrz < aux)
    {
        //fout<<"cauta primeste "<<a<<" "<<b<<" "<<" "<<nrz<<"si returneaza cauta de "<<a<<" "<<(a+b)/2<<" "<<nrz<<"\n";

        return cauta(a,(a+b)/2,nrz);
    }
    else


        if (nrz>aux)
        {
            //fout<<"cauta primeste "<<a<<" "<<b<<" "<<" "<<nrz<<"si returneaza cauta de "<<(a+b)/2<<" "<<b<<" "<<nrz<<"\n";
            return cauta(((a+b)/2)+1,b,nrz);
        }
        else
        {

            //fout<<"cauta returneaza"<<(a+b)/2<<" \n";
            return (a+b)/2;
        }

}

long nrzero ( long x )
{
    long k=0;
    int i;
    for (i=1;(i<=13)&&(x/pt[i]);i++)
        k=k+x/pt[i];
    //fout<<x<<" factorial are "<<k<<"zerouri \n";
    return k;
}