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 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

 

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;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
5 2

Output

x
+
cmd
3
Advertisements

Demonstration


Previous
#2382 Beecrowd Online Judge Solution 2382 Sedex Marciano Solution in C, C++, Java, Js and Python
Next
#2384 Beecrowd Online Judge Solution 2384 Tradutor Alienígena Solution in C, C++, Java, Js and Python