Cod sursa(job #1838035)

Utilizator BLz0rDospra Cristian BLz0r Data 30 decembrie 2016 21:07:11
Problema Factorial Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <fstream>
#include <cmath>
using namespace std;

ifstream fin("fact.in");
ofstream fout("fact.out");

int N;

// functie ce returneaza numarul de factori de 5
// din toate numerele de la 1 la x
int getFact5(int x) {

    int fact5 = 0;

    while (x > 0) {
        fact5 += x / 5;
        x /= 5;
    }

    return fact5;
}

// cautam binar valoarea cautata
int Bsearch() {

    int st = 1, dr = 500000000;

    while (st <= dr) {
        int mid = st + ((dr - st) >> 1);

        int fact5 = getFact5(mid);

        //daca am gasit o valoare ce imi da numarul bun de termeni
        if (fact5 == N)
            return mid - mid % 5; // scot din ea termenii de dupa, care nu au factori de 5

        if (fact5 < N)
            st = mid + 1;
        else
            dr = mid - 1;
    }

    return -1;
}

int main(){

    fin >> N;

    fout << Bsearch();

    return 0 ;
}