Cod sursa(job #2115046)

Utilizator damian.belesDamian-Teodor Beles damian.beles Data 26 ianuarie 2018 11:05:18
Problema Factorial Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <fstream>

int zeroCounter(int iNumber) {
    int iPower = 5, iCounter = 0;
    while (iNumber / iPower) {
        iCounter += iNumber / iPower;
        iPower *= 5;
    }
    return iCounter;
}

int binarySearch(int left, int right, int pivot) {
    while (left <= right) {
        int middle = right + (left - right) / 2;
        if (zeroCounter(middle) == pivot)
            return middle;
        if (zeroCounter(middle) > pivot)
            right = middle - 1;
        else left = middle + 1;
    }
}

int exponentialSearch(int iZeros) {
    int iCurrent, iFoundElement, iCurr;
    for (iCurrent = 1; zeroCounter(iCurrent) < iZeros; iCurrent <<= 1);
    iFoundElement = binarySearch(iCurrent >> 1, iCurrent, iZeros);
    for (iCurr = iFoundElement; zeroCounter(iCurr) == iZeros; iCurr--);
    return zeroCounter(iCurr + 1) == iZeros? iCurr + 1 : -1;
}

int main() {
    int iZeros;
    std::ifstream fin ("fact.in");
    fin >> iZeros;
    std::ofstream fout("fact.out");
    if (iZeros == 0)
        fout << "1\n";
    else fout << exponentialSearch(iZeros) << "\n";
    fout.close();
    return 0;
}