Cod sursa(job #807344)

Utilizator theep0Cruceru Radu theep0 Data 4 noiembrie 2012 16:59:03
Problema Factorial Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 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) {
        /*cout << "left: " << left << endl;
        cout << "middle: " << middle << endl;
        cout << "right: " << right << endl;*/
        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;
    cout << number << endl;
    output.close();
    return 0;
}