Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

ALTAS2 - Altas aventuras

 

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 não 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.

Tarefa

Dados a capacidade máxima da bomba e o número de balões, indicar 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 ≤ K ≤ N ≤ 1.000.000.000).

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.

Exemplo

Entrada
5 2

Saída
3

Entrada
20 2

Saída
6

Entrada
11 5

Saída
4


Adicionado por:Wanderley Guimarăes
Data:2011-04-28
Tempo limite:1s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:OBI 2010 - fase 2 nível 2

hide comments
2015-01-23 20:30:33 Rafael Cabral
Felipe, está realmente errada sua conclusăo no comentário que cita o caminho 11->1->2->3->4->5->6->7->8->9->10?

2012-05-25 16:03:56 Felipe Avelar [UNESP]


Last edit: 2012-05-25 16:04:16
2012-05-10 12:45:37 Felipe Avelar [UNESP]
Entendi, agora, o problema. (:
2012-05-09 21:59:05 Felipe Avelar [UNESP]
Mas ele năo pede o PIOR caso, dentre TODOS? o.o'
2012-05-09 21:56:52 Marcos Kawakami
Năo. Se começar pelo 11, a resposta é 11 no pior caso. Mas se vocę começar por outro valor, o pior caso pode ter valor menor.
2012-05-09 21:46:35 Felipe Avelar [UNESP]
Eu năo quero dar a resposta por aqui, entăo, se eu tiver fugindo de alguma das regras podem(e devem) apagar o comentário, mas o caso dois năo ficaria:
11->1->2->3->4->5->6->7->8->9->10?
Se tiver fugindo as regras, por favor apague.
2012-05-09 21:14:18 Marcos Kawakami
Os casos de teste deste problema estavam fracos. Todos as submissőes foram rejulgadas. A soluçăo oficial retorna 6 para o segundo exemplo.
Para o segundo caso, é possível descrever uma forma de realizar o experimento de forma que no *pior* caso, o número de testes é 6. Ou seja, este experimento *sempre* realiza um número de testes menor ou igual a 6. Além disso, é impossível garantir um número de testes menor ou igual a 5. Portanto, a resposta é 6.

Last edit: 2012-05-09 21:31:58
2012-05-09 10:30:02 Felipe Avelar [UNESP]
A saída dois năo tá certa. Já que ele pede o pior caso, o pior caso seriam 11 testes e năo 6. Caso o primeiro balăo estoure na primeira tentativa...

Last edit: 2012-05-09 11:22:21
2012-05-09 01:14:44 Marcos Kawakami
A saída do caso 2 está certa. É possível garantir um número de testes inferior ou igual a 6.

Last edit: 2012-05-09 02:39:08
2012-05-06 06:12:13 Alan Peixinho [UNESP]
O caso 2 está errado, a saída correta é 11
algo me diz que alguém fez ou bit a bit com o operador ^ tentando fazer potencia :-)

Last edit: 2012-05-06 06:12:35
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.