Cod sursa(job #1510066)

Utilizator DeehoroEjkoliPop Darian DeehoroEjkoli Data 24 octombrie 2015 15:29:23
Problema Factorial Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <fstream>
using namespace std;
ifstream fin("fact.in");
ofstream fout("fact.out");

int p;

int powFiveSmallerThanX(int x) {
    int n = 5, pow = 1;
    while (n <= x) {
        ++pow;
        n *= 5;
    }
    --pow;
    return pow;
}

int howManyFives(int x) {
    int w = 5, s = 0;
    for (int i = 1; i <= powFiveSmallerThanX(x); ++i) {
        s += x / w;
        w *= 5;
    }
    return s;
}

void binarySearch() {
    int lmtL = 5, lmtR = p * 5;
    int pivot = (lmtL + lmtR) / 2;
    while (howManyFives(pivot) != p) {
        if (howManyFives(pivot) > p) {
            lmtR = pivot;
            pivot = (lmtL + lmtR) / 2;
            if (lmtL == lmtR - 1) {
                if (howManyFives(lmtR) == p)
                    fout << lmtR;
                else fout << "-1";
                return;
            }
        }
        else {
            lmtL = pivot;
            pivot = (lmtL + lmtR) / 2;
            if (lmtL == lmtR - 1) {
                if (howManyFives(lmtR) == p)
                    fout << lmtR;
                else fout << "-1";
                return;
            }
        }
    }
    if (howManyFives(pivot - 1) == p) --pivot;
    while (pivot % 5 != 0)
        --pivot;
    fout << pivot;
}

int main()
{
    fin >> p;
    if (p == 0) fout << 1;
    else binarySearch();
    return 0;
}