11753. Investindo no mercado de ações 1

Olá, desculpem-me meus amigos nerds mas essa semana não tive tempo de resolver nenhum problema junto com vocês (problemas mais desafiadores me atacaram). Mesmo assim, para não deixar passar em branco a semana mais divertida da copa (valeu Costa Rica e Chile), passei aqui para resolver mais um probleminha.

Investir no mercado de ações não é algo simples, normalmente exige tempo e atenção. Mesmo assim, nesse problema, vamos ter a oportunidade de ver como nosso amigo João investe de uma forma engraçada e peculiar. O problema 11753. Investindo no mercado de ações 1 nos pede para ajudar João a determinar em quantas partes ele deve dividir seu dinheiro para que ele obtenha um investimento mais seguro (pelo menos na opinião dele).

Modelagem

O problema nos pede para contar em quantas partes precisamos dividir N reais até que tenhamos apenas partes de no máximo k reais. Sendo que a divisão deve ser feita recursivamente em duas partes iguais a ⌊N/2⌋ e ⌈N/2⌉, até restar apenas partes de no máximo k reais.

Observe que, uma leitura atenta do problema já nos indica um algoritmo para resolvê-lo. Seja conta(N), o número de partes que devemos dividir N, assim temos nossa recursão:

conta(N) = conta(⌊N/2⌋) + conta(⌈N/2⌉) se N > k
conta(N) = 1                           se N <= k

Pronto, basta implementar essa recursão e o problema de João está resolvido. Sem graça, né? Então, vamos explorar um pouco mais esse problema? Vamos brincar de derivar a complexidade da nossa solução?

É possível achar uma fórmula fechada para essa recursão, entretanto fazer isso é complicado, pois teríamos que lidar com ⌊N/2⌋, o que não é simples. Observe, entretanto que a solução para um problema de tamanho N depende da solução de um problema de tamanho N/2, então a complexidade de nossa recursão é provavelmente logarítmica.

Para comprovar nossa hipótese de que o número de passos de nossa recursão é logarítmico, suponha que N seja uma potência de 2 (N=2^h), assim ⌊N/2⌋ e ⌈N/2⌉ serão iguais, logo temos:

conta(N)         = 2*conta(N/2) <=> conta(N/2^0) = 2*conta(N/2^1)
conta(N/2)       = 2*conta(N/4) <=> conta(N/2^1) = 2*conta(N/2^2)
...
conta(N/2^(h-1)) = 2*conta(N/2^h)

logo nossa recursão terá profundidade h. Mas h = log2(N). Assim a complexidade do nosso algoritmo é logarítmica. E como você já deve ter ouvido, em algum lugar, que algoritmos de complexidade logarítimica são eficientes vamos implementá-lo, então!

Implementação

O código abaixo, implementa nossa solução. Observe que ⌊N/2⌋ e ⌈N/2⌉ são simples de calcular (basta saber se N é par ou ímpar!).