1936 - Fatorial

Vamos resolver esse problema gulosamente (apesar de estarmos na categoria Ad Hoc).

Descrição

Solução

Aqui estamos interessados em saber o mínimo de fatoriais necessários para somar um determinado número, o que pode ser feito de maneira gulosa, ou seja, considerando todas as parcelas do maior fatorial possível dentro do número e assim sucessivamente até que alcance o número passado.

Por exemplo, para o número 10, o maior fatorial menor que 10 é 3! e é possível encaixar apenas uma dessa parcela, sobrando 4. Para o número 4, o maior fatorial menor que 4 é 2! e é possível encaixar duas parcelas de 2!, sobrando 0. Logo, o número total de parcelas mínimo necessário é 3 (3! + 2! + 2!).

Pré-calcular os fatoriais até 100.000 vai simplificar bastante nosso código.

#include <stdio.h>

int main()
{
    int N, resultado;
    int fatoriais[] = {40320, 5040, 720, 120, 24, 6, 2, 1};

    scanf("%d", &N);

    resultado = 0;
    for (int i = 0; i < 8; ++i)
    {
        resultado += N / fatoriais[i];
        N %= fatoriais[i];
    }

    printf("%d\n", resultado);

    return 0;
}

#include <iostream>

using namespace std;

int main()
{
    int N, resultado;
    int fatoriais[] = {40320, 5040, 720, 120, 24, 6, 2, 1};

    cin >> N;

    resultado = 0;
    for (int i = 0; i < 8; ++i)
    {
        resultado += N / fatoriais[i];
        N %= fatoriais[i];
    }

    cout << resultado << endl;

    return 0;
}

var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var lines = input.split('\n');

const fatorial = [40320, 5040, 720, 120, 24, 6, 2, 1];

let N = parseInt(lines.shift());

let resultado = 0;
for(let i = 0; i < fatorial.length; ++i){
    resultado += Math.floor(N/fatorial[i]);
    N %= fatorial[i];
}

console.log(resultado);

Previous1893 - Fases da Lua Next1940 - Jogo da Estratégia

Last updated 4 years ago

Was this helpful?