Cod sursa(job #1981936)

Utilizator flaviu_2001Craciun Ioan-Flaviu flaviu_2001 Data 17 mai 2017 11:00:48
Problema Factorial Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
/*
    ELEV: CRACIUN FLAVIU

    Aceasta implementare calculeaza puterea lui 5 din n factorial,
    deoarece puterile lui 5 sunt mai putin numeroase decat puterile lui 2
    astfel calculeaza din 5 in 5 si daca x e egal cu p atunci returneaza i

    COMPLEXITATE: O(P) unde p e numarul dat in problema
*/

#include <iostream>
#include <fstream>

using namespace std;

int cinciuri(int x)
{
    int k = 0;
    while(x%5==0)
        ++k,
        x /= 5;
    return k;
}

int zerouri(int x)
{
    int k = 0;
    while(x){
        k += x/5;
        x /= 5;
    }
    return k;
}

int functia_cu_p(int x)
{
    int hi = x * 5, lo = x*4, m;
    for (m = (lo+hi)/2; lo <= hi; m = (lo+hi)/2){
        int y = zerouri(m);
        if(y == x)
            return m-m%5;
        else if (y > x)
            hi = m-1;
        else lo = m+1;
    }
    return -1;
}

int main()
{
    ifstream fin ("data.in");
    ofstream fout ("data.out");
    int p;
    fin >> p;
    fout << functia_cu_p(p);
    fin.close();
    fout.close();
    return 0;
}