Cod sursa(job #1837971)

Utilizator patrixKovacs Patrik patrix Data 30 decembrie 2016 18:23:23
Problema Factorial Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
/*
	kpim1636
	Kovacs Patrik
	group: 512
	http://www.infoarena.ro/problema/fact
*/

#include <fstream>

//#define CONSOLE

#ifdef CONSOLE
#include <iostream>
#define f std::cin
#define g std::cout
#endif

unsigned exponent (unsigned n, unsigned k) {

    unsigned t = n / k;
    unsigned a = k;
    unsigned sum = 0;
    while (t) {
        sum += t;
        a *= k;
        t = n / a;
    }
    return sum;
}

unsigned binary_search (unsigned left, unsigned right, int p) {

    if (left > right)
        return -1;

    /*if (left == right) {

        if (exponent(left, 5) == p)
            return left;
        else
            return -1;
    }*/

    unsigned mid = (left + right) / 2;
    unsigned k = exponent(mid, 5);

    if (k > p)
        return binary_search(left, mid-1, p);
    else if (k < p)
        return binary_search(mid+1, right, p);
    else {
        unsigned t = binary_search(left, mid-1, p);
        if (t != -1)
            return t;
        else
            return mid;
    }
}

int main () {
    #ifndef CONSOLE
    std::ifstream f ("fact.in");
    std::ofstream g ("fact.out");
    #endif

    int p;
	f >> p;

    if (!p) {
        g << 1;
        return 0;
    }

	g << (int) binary_search(0, 1000000000, p);
}