Solução por Pedro Racchetti
Contéudo utilizado:
Para esse problema, podemos ver que é possível calcular a resposta recursivamente, já que quando testarmos a pressão em valor $$x$$ e $$k$$ telefones, pode-se-ter dois casos:
- o telefone dobra, tendo então que usar $$k – 1$$ telefones, na pressão $$x – 1$$;
- O telefone não dobra, tendo então que usar o mesmo número de telefones, para pressões $$x + 1$$ até $$m$$, com $$k$$ telefones
Perceba que o segundo caso, é equivalente a testar no intervalo de $$1$$ até $$m – x$$. A recursão $$f(x, k)$$ portanto é a seguinte, sendo $$k$$ o número de telefones e $$x$$ a pressão atual:
- $$f(x, 1) = x$$, já que com um telefone é necessário usar todas as pressões abaixo, no pior caso;
- $$f(0, k) = 0$$, já que com pressão $$0$$ nenhum telefone irá quebrar;
- $$f(1, k) = 1$$ já que basta apenas testar em $$1$$ para pressão $$1$$
- $$f(x, k) = min(max(f(i – 1, k – 1), f(x – i, k)) + 1)$$ para todo $$i$$ no intervalo $$[ 1, x [$$.
Porém, se apenas usarmos uma função recursiva, a complexidade ficará exponencial, não passando devido a tempo. Para corrigir isso, podemos usar programação dinâmica para armazenar os valores já calculados. Note também que não podemos calcular todos os valores em cada caso de teste, obrigando o cálculo da programação dinâmica a ser feito antes do processamento dos casos de testes.
Segue o código para melhor compreensão:
https://gist.github.com/PedroRacchetti/9d914622498dd1f3bd31187b8e4fbddb