Cod sursa(job #807353)

Utilizator theep0Cruceru Radu theep0 Data 4 noiembrie 2012 17:11:16
Problema Factorial Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <iostream>
#include <fstream>

using namespace std;

long long number_of_zeros(long long number) {
    long long zeros = 0;
    while (number / 5) {
        zeros += number / 5;
        number /= 5;
    }
    // cout << "zeros: " << zeros << endl;
    return zeros;
}

long long binary_search(long long left, long long right, long long p) {
    long long middle;
    long long zeros;
    long long solution = 0;
    bool found = false;
    while (left < right) {
        middle = right - (right - left) / 2;
        zeros = number_of_zeros(middle);
        if (zeros > p) {
            right = middle - 1;
        }
        if (zeros < p) {
            left = middle + 1;
        }
        if (zeros == p) {
            solution = middle;
            found = true;
            if (right == middle) {
                --right;
            } else {
                right = middle;
            }
        }
    }
    if (found) {
        return solution;
    } else {
        return -1;
    }
}

int main() {
    long long left = 0;
    long long right = 1000000000LL;
    long long p;
    long long number;
    ifstream input;
    ofstream output;

    input.open("fact.in");
    input >> p;
    input.close();

    if (p == 0) {
        number = 1; 
    } else {
        number = binary_search(left, right, p);
        if (number != -1) {
           for (; number_of_zeros(number) == p; --number); 
           ++number;
        }
    }
    output.open("fact.out");
    output << number;
    output.close();
    return 0;
}