Cod sursa(job #1510035)

Utilizator DeehoroEjkoliPop Darian DeehoroEjkoli Data 24 octombrie 2015 15:02:52
Problema Factorial Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 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 (true) {
        if (howManyFives(pivot) >= p) {
            lmtR = pivot;
            pivot = (lmtL + lmtR) / 2;
            if (lmtL == lmtR - 1) {
                fout << lmtR;
                return;
            }
        }
        else if (howManyFives(pivot) < p) {
            lmtL = pivot;
            pivot = (lmtL + lmtR) / 2;
            if (lmtL == lmtR - 1) {
                fout << lmtR;
                return;
            }
        }
    }
}

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