URI Online Judge | 2383

Altas Aventuras

Por OBI - Olimpíada Brasileira de Informática, 2010 BR Brazil

Timelimit: 1

Incentivado por um filme de animação recente, vovô resolveu realizar seu sonho de criança, fazendo sua pequena casa voar amarrada a balões de hélio. Comprou alguns balões coloridos de boa qualidade, para fazer alguns testes, e começou a planejar a grande aventura. A primeira tarefa é determinar qual a quantidade de hélio máxima que pode ser injetada em cada balão de maneira que ele nao estoure.

Suponha que os valores possíveis de quantidade de hélio em cada balão variem entre os valores 1 e N. Claro que vovô poderia testar todas as possibilidades, mas esse tipo de solução ineficiente não é apropriada, ainda mais considerando que vovô comprou apenas K balões para os testes.

Por exemplo, suponha que N = 5 e K = 2. Nesse caso, a melhor solução seria testar primeiro em 3. Caso o balão estoure, vovô só teria mais um balão, então teria de testar 1 e 2 no pior caso, somando ao todo 3 testes. Caso o balão não estoure, vovô poderia testar 4 e depois 5 (ou 5 e depois 4), também somando 3 ao todo.

Dados a capacidade máxima da bomba e o número de balões, indique o número mínimo de testes que devem ser feitos, no pior caso, para determinar o ponto em que um balão estoura.

Entrada

A única linha da entrada contém dois inteiros, N e K, separados por espaço em branco (1 ≤ KN ≤ 109).

Saída

Seu programa deve imprimir uma única linha, contendo um inteiro que representa o número mínimo de testes que devem ser feitos no pior caso para determinar o ponto em que o balão estoura.

Exemplos de Entrada Exemplos de Saída

5 2

3

20 2

6

11 5

4