Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2383
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2383
Altas Aventuras
Por OBI - Olimpíada Brasileira de Informática, 2010 
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 ≤ K ≤ N ≤ 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 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 300;
int dp[MAXN][MAXN], N, K;
int solve(int tam, int resta) {
if (dp[tam][resta] != -1) return dp[tam][resta];
if (tam == 0 || resta == 1) return dp[tam][resta] = tam;
int best = tam;
for (int testa = 1; testa < = tam; testa++) {
best = min(best, 1 + max(solve(testa - 1, resta - 1),
solve(tam - testa, resta)));
}
return dp[tam][resta] = best;
}
int main() {
cin >> N >> K;
int logaritmo = (int)ceil(log2(N));
if (K >= logaritmo) {
cout << logaritmo << endl;
return 0;
}
memset(dp, -1, sizeof(dp));
cout << solve(N, K) << endl;
return 0;
}
Input
Output