Cod sursa(job #2772421)

Utilizator Gabryel9898Bizdoc Vasile Gabriel Gabryel9898 Data 1 septembrie 2021 04:11:27
Problema Factorial Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <iostream>
#include <chrono>
#include <fstream>
#include <unordered_map>
#include <cstdlib>

using namespace std::chrono;

long long zeros(long long n) {
    static std::unordered_map<long long, long long> zeros_cache;
    try {
        return zeros_cache.at(n);
    }
    catch (...) {
        long long res = 0;
        while ((n = n / 5)) {
            res += n;
        }
        zeros_cache[n] = res;
        return res;
    }
}


void factorial() {
    std::ifstream f1;
    std::ofstream f2;


    int target;


//    f1.open("../in.txt");
//    f2.open("../out.txt");
    f1.open("fact.in");
    f2.open("fact.out");

    f1 >> target;

    long long start = 1;
    long long end = 400000015;
    long long number_of_zeroes;
    long long half;

    do {
        half = (start + end) / 2;
        number_of_zeroes = zeros(half);
        if (number_of_zeroes >= target) {
            end = half;
        } else if (number_of_zeroes < target) {
            start = half + 1;
        }
    } while (start != end);

    if (zeros(start) == target) {
        f2 << start;
    } else {
        f2 << -1;
    }
}


int main() {
    auto start = high_resolution_clock::now();

    factorial();

    auto stop = high_resolution_clock::now();
    auto duration = duration_cast<milliseconds>(stop - start);
    std::cout << std::endl << "[time]:" << duration.count() << std::endl;
    return 0;
}