Cod sursa(job #1984773)

Utilizator savigunFeleaga Dragos-George savigun Data 25 mai 2017 22:47:22
Problema Factorial Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <iostream>
#include <fstream>
using namespace std;

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

int p, five[14];

void preprocess() {
    five[1] = 5;
    for (int i = 2; i <= 13; ++i) {
        five[i] = 5 * five[i - 1];
    }
}


int binary_search(int a, int b) {
    if (a > b) return -1;
    int mid = (a + b) >> 1;

    int zeros = 0;
    int i = 1;
    while (five[i] <= mid) {
        zeros += mid / five[i];
        i++;
    }
    if (zeros == p) return mid;

    if (zeros > p) return binary_search(a, mid);
    return binary_search(mid + 1, b);
}


int main() {
    in >> p;

    if (p == 0) {
        out << 1;
        return 0;
    }

    preprocess();

    int sol = binary_search(1, 1e8 * 5);

    if (sol == -1) {
        out << -1;
        return 0;
    }


    sol -= sol % 5;
    out << sol;
}