URI (BEECROWD) - 1936 - Fatorial - Ad-Hoc - C

Plataforma: URI (BEECROWD)

Problema: 1936

Enunciado:

O fatorial de um número inteiro positivo N, denotado por N!, é definido como o produto dos inteiros positivos menores do que ou iguais a N. Por exemplo 4! = 4 × 3 × 2 × 1 = 24.

Dado um inteiro positivo N, você deve escrever um programa para determinar o menor número k tal que N = a1! + a2! + ... + ak!, onde cada ai, para 1 ≤ i ≤ k, é um número inteiro positivo.

Por exemplo, para N = 10 a resposta é 3, pois é possível escrever N como a soma de três números fatoriais: 10 = 3! + 2! + 2!. Para N = 25 a resposta é 2, pois é possível escrever N como a soma de dois números fatoriais: 25 = 4! + 1!.

Linguagem: C

Solução:

#include <stdio.h>
int main() {
    
    int fatoriais[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320};
    int n, i = 8, c = 0;
    scanf("%d", &n);
    
    while (n) {
        if (n >= fatoriais[i]) {
            c++;
            n -= fatoriais[i];
        }
        else
            i--;
    }
    
    printf("%d\n", c);

    return 0;
}