Cod sursa(job #1660793)

Utilizator Alexghita96Ghita Alexandru Alexghita96 Data 23 martie 2016 13:58:45
Problema Factorial Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
/**
 * Programul porneste de la urmatoarea observatie: pentru ca N! sa aiba P 0-uri, el trebuie sa aiba
 * P 5-uri in descompunerea in factori primi, deoarece pentru fiecare 0 este necesar un 10 in produs,
 * iar cum 10 = 2 * 5 si produsul va avea intotdeauna suficienti 2, conteaza doar numarul de 5-uri.
 * Astfel, programul porneste cu N de la 0, adunand 0-uri (adica cate 5 la N) sau grupe de 6 0-uri
 * (adica cate 25 la N), cand este posibil, pana cand numarul de 0-uri astfel obtinut este mai mare
 * sau egal cu P. Daca numarul de 0-uri obtinut este mai mare decat P, programul va afisa -1, altfel
 * va afisa N. De asemenea, la fiecare adunare, programul mai verifica pentru 5-uri suplimentare care
 * pot aparea din obtinerea unui multiplu a unei puteri de 5 mai mare (de exemplu, 125, 625 etc.).
 */

#include <iostream>
#include <fstream>

using namespace std;

int P;
int N = 0;
int trailingZeros = 0; // numarul de 0-uri curent

void solve() {
    while (trailingZeros < P) {
        int aux;

        // atunci cand se poate, programul aduna "grupe" de sase 0-uri pentru a scurta timpul de executie
        if (trailingZeros + 6 < P) {
            N += 25;
            trailingZeros += 6;
            aux = N / 25;
        }
        // altfel, aduna doar un 0
        else {
            N += 5;
            aux = N;
        }

        // verificare pentru eventuale puteri mai mari ale lui 5
        while (aux % 5 == 0) {
            aux /= 5;
            trailingZeros++;
        }
    }

    // daca numarul de 0-uri gasit este mai mare decat P, inseamna ca nu exista raspuns pentru acest P
    if (trailingZeros > P) {
        cout << -1;
    }
    else {
        cout << N;
    }
}

int main() {
    freopen("fact.in", "r", stdin);
    freopen("fact.out", "w", stdout);

    cin >> P;
    // caz special pentru P = 0
    if (P == 0) {
        cout << 1;
        return 0;
    }

    solve();
}