Cod sursa(job #1984761)

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

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

int p, five[13], maxpower;

void preprocess() {
    int power = 1;
    for (int i = 1; i <= 12; ++i) {
        power *= 5;
        five[i] = power;
    }
}

int get_zeros(int n) {
    int zeros = 0;
    int i = 1;
    while (five[i] <= n) {
        zeros += n / five[i];
        i++;
    }
    return zeros;
}

bool possible(int n) {
    int zeros = get_zeros(n);
    if (zeros <= p) return true;
    return false;
}

int binary_search() {
    int step = 1 << 27;
    int p = 0;
    while (step) {
        if (p + step <= 1e8 && possible(p + step)) {
            p += step;
        }
        step /= 2;
    }

    return p;
}


int main() {
    in >> p;

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

    preprocess();

    int sol = binary_search();
    while (sol % 5 != 0) {
        sol--;
    }

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

    out << sol;
}