Cod sursa(job #2610216)

Utilizator anacomoAna-Maria Comorasu anacomo Data 4 mai 2020 17:20:02
Problema Factorial Scor 95
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <iostream>
#include <fstream>
#include <math.h>

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

int N;

int trailingzeros(int n)
{
    unsigned int coef = 5;
    int count = 0;
    while(n / coef)
    {
        count += n / coef;
        coef *= 5;
    }
    return count;
}

int main()
{

    fin >> N;
    //cin >> N;
    // binary search
    if(N < 0)
    {
        fout << -1;
        return 0;
    }
    int left = N;
    int right = 10 * N;
    int middle;

    while(left < right)
    {
        middle  = (left + right) / 2;
        int zeros = trailingzeros(middle);
        if(zeros == N)
        {
            while(trailingzeros(middle - 1) == zeros)
                middle--;
            fout << middle;
            return 0;
        }
        else if(zeros < N)
            left = middle + 1;
            else
            {
                right = middle -1;
            }
            
    }

    fout << -1;
    return 0;
}