Cod sursa(job #1510002)

Utilizator DeehoroEjkoliPop Darian DeehoroEjkoli Data 24 octombrie 2015 14:51:43
Problema Factorial Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 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 * 100;
    int pivot = (lmtL + lmtR) / 2;
    while (howManyFives(pivot) != p) {
        if (howManyFives(pivot) > p) {
            lmtR = pivot;
            pivot = (lmtL + lmtR) / 2;
            if (lmtL == lmtR - 1) {
                fout << lmtR;
                return;
            }
        }
        else {
            lmtL = pivot;
            pivot = (lmtL + lmtR) / 2;
            if (lmtL == lmtR - 1) {
                fout << lmtR;
                return;
            }
        }
    }
    while (pivot % 5 != 0)
        --pivot;
    fout << pivot;
}

int main()
{
    fin >> p;
    binarySearch();
    return 0;
}