1441 - Sequências de Granizo
Mais um dia, mais um problema Ad Hoc...
Descrição
Solução
Como os limites desse problema são bem baixos (números entre 1 e 500), é perfeitamente possível resolver este problema com pura simulação. Outra alternativa seria usar memorização para não precisar fazer várias vezes a recorrência com o mesmo número e pegar atalhos quando alguns números caírem em outros números já memorizados, mas para essa solução, seria necessário usar um dicionário para armazenar as respostas, já que não sabemos qual o maior número possível em uma sequência.
Alternativa 1 - Sem memorização
#include <stdio.h>
int main()
{
int n, resposta;
while (scanf("%d", &n))
{
if (!n)
break;
resposta = n;
while (n > 1)
{
if (n % 2)
n = 3 * n + 1;
else
n /= 2;
resposta = n > resposta ? n : resposta;
}
printf("%d\n", resposta);
}
return 0;
}
Alternativa 2 - Com memorização
Fazer uma solução recursiva como essa estoura o limite de recursão em Python.
#include <stdio.h>
int respostas[100001];
int max(int a, int b)
{
return a > b ? a : b;
}
int H(int n)
{
if (respostas[n] == -1)
{
if (n % 2)
respostas[n] = max(n, H(3 * n + 1));
else
respostas[n] = max(n, H(n / 2));
}
return respostas[n];
}
int main()
{
int n;
respostas[0] = 1;
respostas[1] = 1;
for (int i = 2; i < 100001; ++i)
{
respostas[i] = -1;
}
while (scanf("%d", &n))
{
if (!n)
break;
printf("%d\n", H(n));
}
return 0;
}
Last updated
Was this helpful?