Cod sursa(job #870351)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 3 februarie 2013 12:07:05
Problema Factorial Scor 75
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.29 kb
#include <fstream>
#include <cmath>

using namespace std;

//Acest vector retine primele 12 puteri ale lui 5, inclusiv 5^0=1
int puteri_5[12]={1,5,25,125,625,3125,15625,78125,390625,1953125,9765625,48828125};

//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; //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=5*p;
    
    //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=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;
}