Cod sursa(job #2659966)

Utilizator catalin69420Gogu Popescu catalin69420 Data 17 octombrie 2020 22:16:03
Problema Factorial Scor 10
Compilator c-64 Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <stdio.h>

// use a type that can hold numbers between 0 and 10^8
typedef unsigned long long ulong;


// count trailing zeros in n's factorial
// using this formula
// trailing0s = floor(n/5) + floor(n/25) + floor(n/125) + ...
// we'll stop when floor(n / pow(5, x)) == 0
int countTrailingZeros(ulong n) {
    int count = 0;

    for (ulong i = 5; n / i >= 1; i *= 5) {
        count += n / i;
    }

    return count;
}

// we can observe that for every number n
// 5 * n contains at least n trailing zeros
// search to numbers from 0 to 5 * n
// using binary search
ulong solve(int n) {
    if (n < 0)
        return 0;

    // base cases
    if (n == 0)
        return 1;

    if (n == 1)
        return 5;

    ulong low = 2;
    ulong high = 5 * (ulong)n;

    // iterative implementation
    // to reduce memory usage
    while (low < high) {
        ulong mid = (low + high) / 2;

        if (countTrailingZeros(mid) >= n)
            high = mid;
        else
            low = mid ;
    }

    return low;
}

int main() {
    FILE* in, *out;
    in = fopen("fact.in", "r");
    if (!in) {
        fprintf(stderr, "Error while opening fact.in, check if file exists!\n");
        return 0;
    }

    out = fopen("fact.out", "w");

    if (!out) {
        fprintf(stderr, "Error while opening fact.out\n");
        fclose(in);
        return 0;
    }

    int n;
    fscanf(in, "%d", &n);

    fprintf(out, "%llu\n", solve(n));

    fclose(in);
    fclose(out);

    return 0;
}