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!
).
#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;
}
Last updated
Was this helpful?