Cod sursa(job #1984767)

Utilizator savigunFeleaga Dragos-George savigun Data 25 mai 2017 22:39:17
Problema Factorial Scor 15
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 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 <= 13; ++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 a, int b) {
    if (a > b) return -1;
    int mid = (a + b) / 2;

    int zeros = get_zeros(mid);
    if (zeros == p) return mid;

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


int main() {
    in >> p;

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

    preprocess();

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

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


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