Cod sursa(job #870417)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 3 februarie 2013 13:15:45
Problema Factorial Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.35 kb
#include <fstream>
#include <cmath>
 
using namespace std;
 
//Acest vector retine primele 12 puteri ale lui 5, inclusiv 5^0=1
int puteri_5[]={1,5,25,125,625,3125,15625,78125,390625,1953125,9765625,48828125,244140625,1220703125};
 
//Aceasta functie determina cati de 0 are x! la sfarsit
int nr_factori_10(int x)
{
    //Initial, nu are 0-uri
    int raspuns=0;
     
    //i - contor
    int i;
     
    //Folosind Formula lui Legendre si faptul ca daca avem destui 5, avem sigur si destui 2
    //calculam cati de 0 are x! la sfarsit
    for(i=1;i<12 && puteri_5[i]<=x;i++)
        raspuns+=(floor(x/puteri_5[i]));        
     
    //Intoarcem raspunsul
    return raspuns;
}
 
int main()
{
    //Deschidem fisierele de intrare si iesire
    ifstream fin("fact.in");
    ofstream fout("fact.out");
 
    //P-ul din enunt
    int p;
     
    //Citim numarul de 0-rui cerut
    fin>>p;
     
    //Daca acesta este 0, nu putem afisa 0 (caci 0!=1, dar 0 nu este strict pozitiv), ci 1
    if(p==0)
    {
        fout<<"1\n";
         
        //Inchidem fisierele de intrare si iesire 
        fin.close();
        fout.close();
        return 0;        
    }
     
    //Cautam binar valoarea ceruta
    long long int cap=1; //Se pleaca de la 1!=1
    long long int coada=5*p+10; //La (5*p)!, caci acesta are sigur minim p de 0 la sfarsit (din Formula lui Legendre)
    long long int mijl=(cap+coada)/2;
     
    //In rezultat vom tine cel mai mic rezultat obtinut
    long long int rezultat=-1;
     
    //Cautarea binara propriu-zisa
    while(cap<=coada)
    {
        //Daca are fix p de 0 la sfarsit, verificam daca poate fi solutie
        if(nr_factori_10(mijl)==p)
        {
            if(mijl<rezultat || rezultat==-1)
               rezultat=mijl;
            coada=mijl-1;                       
        }
        else if(nr_factori_10(mijl)>p) //Daca nu are, avem cele doua cazuri clasice ale cautarii binare
        {
            coada=mijl-1;                    
        }
        else
        {
            cap=mijl+1;
        }
         
        //Facem update la mijloc
        mijl=(cap+coada)/2;                           
    } 
     
    //Afisam rezultatul
    fout<<rezultat<<'\n';
     
    //Inchidem fisierele de intrare si iesire
    fin.close();
    fout.close();
    return 0;
}