Cod sursa(job #2793314)

Utilizator christalknightChristian Micea christalknight Data 3 noiembrie 2021 14:24:16
Problema Factorial Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.93 kb
#include <iostream>
#include <fstream>

using namespace std;

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

unsigned long long cautare_binara(unsigned long long P, unsigned long long high, unsigned long long low);
unsigned long long cautare_nr_zerouri(unsigned long long a);
unsigned long long binary_srch(unsigned long long P, unsigned long long high, unsigned long long low);

int main()
{
    /*unsigned long long N = 1, P, i, boolean_var = 0;
    fin>>P;
    for(i = 1; P > 0; i += 5){
        N = i;
        while(N % 5 == 0){
            N /= 5;
            P--;
            }
        if(i == 1)
            i--;
        if(P < 0){
            boolean_var = 1;
            break;
            }
        else if(!P)
            break;
        }
    if(boolean_var)
        fout<<-1;
    else fout<<i;*/

    /*unsigned long long P, x, high;
    cin>>P;
    high = P * 5 + P / 5;
    cout<<"high = "<<high<<endl;
    x = cautare_binara(P, high, 1);
    if(x)
        cout<<x;
    else cout<<-1;*/

    unsigned long long P, high;
    cin>>P;
    if(!P)
        cout<<1;
    else{
        high = P * 5 + P / 5;
        cout<<binary_srch(P, high, 1);
        }
}

unsigned long long binary_srch(unsigned long long P, unsigned long long high, unsigned long long low){
    //caut factorialul care are P zerouri la fin: fac cautare binara pt N!
    unsigned long long mid, nr_cerut = 0, i_copie, i;
    //cout<<"high = "<<high<<", low = "<<low<<endl;
    mid = (high + low) / 2 + 1;
    //cout<<"mid = "<<mid<<endl;
    for(i = 1; i <= mid; i += 5){
        i_copie = i;
        while(i_copie % 5 == 0){
            i_copie /= 5;
            nr_cerut++;
            }
        if(i == 1)
            i--;
        }
    if(nr_cerut == P)
        return i - 5;
    else if(nr_cerut > P)
        return binary_srch(P, mid, low);
    else return binary_srch(P, high, mid);
    }

/*unsigned long long cautare_binara(unsigned long long P, unsigned long long high, unsigned long long low){
    unsigned long long i, mid, x;
    cout<<"high = "<<high<<", low = "<<low<<endl;
    mid = (high + low) / 2;
    cout<<"mid = "<<mid<<endl;
    x = cautare_nr_zerouri(mid);
    cout<<"x = "<<x<<endl;
    if(x == 0)
        return 0;
    if(x > P)
        return cautare_binara(P, mid, low);
    else if(x < P)
        return cautare_binara(P, high, mid);
    else return mid;
    }

unsigned long long cautare_nr_zerouri(unsigned long long a){
    unsigned long long i, i_copie, nr_cerut = 0;
    cout<<"a = "<<a<<endl;
    for(i = 1; nr_cerut < a; i += 5){
        i_copie = i;
        while(i_copie % 5 == 0){
            i_copie /= 5;
            nr_cerut++;
            }
        if(i == 1)
            i--;
        cout<<"i = "<<i<<", nr_cerut = "<<nr_cerut<<endl;
        if(nr_cerut > a)
            return 0;
        else if(nr_cerut >= a)
            return i;
        }
    return 0;
    }*/