Cod sursa(job #2610736)

Utilizator stanbianca611Stan Bianca stanbianca611 Data 5 mai 2020 16:26:36
Problema Factorial Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f ("fact.in");
ofstream g ("fact.out");
int n, minn=100000005;
int nr_zerouri(int n)
{
    int putere=5;
    int sum=0;
    while(n/putere)
    {
        sum+=n/putere;
        putere=putere*5;
    }
    return sum;
}
void cautare_binara(int k, int st, int dr, int& minn)
{
    if(st<=dr)
    {
        int putere=5;
        int mij=(st+dr)/2;
        int sum=nr_zerouri(mij);
        //cout<<mij<<" "<<sum<<"\n";
        if(sum==k)
        {
            if(minn>mij)
                minn=mij;
            while(nr_zerouri(mij-1)==k)
            {
                mij--;
                minn=mij;
            }
        }
        else if (sum>k) cautare_binara(k, st, mij-1, minn);
        else cautare_binara(k, mij+1, dr, minn);
    }
}
int main()
{
    f>>n;
    if(n==0) g<<1;
    else {cautare_binara(n, 0, 10*n, minn);
    if(minn==100000005) g<<-1;
    else g<<minn;
    ;}
    return 0;
}