Obi 2007 Nível1 Fase2 - Metro

Autora da análise: arianehaselmann

/* Colocarei o link do problema aqui assim que o bombonera voltar a funcionar. */

Resumo

Dado um certo N representando um número de pessoas, e K paẽs de tamanhos diferentes obter o maior tamanho possível de pedaço de pão tal que todas as N pessoas recebam pedaços de pães com esse tamanho.

Solução

Devemos observar as seguintes condições ao vermos o problema, para isso vamos usar algumas variáveis:

• TamMax = o maior tamanha possível do pedaço de pão
• N = número de pessoas
• Ini = inicio
• Fim = fim
• Max = maior pedaço

Sabemos inicialmente que o maior pedaço possível não será maior do que o maior pedaço ( TamMax $\leq$ Max ) e o menor tamanho possível será 1. Assim temos um intervalo de possíveis tamanhos:

(1)

\begin{align} 1 \leq X \leq \mathrm{Max} \end{align}

A partir daí queremos saber qual o tamanho máximo, se sortearmos um número Y qualquer dentro desse intervalo sabemos que se for possível cortar N pedaços de tamanho Y ele pode ser o TamMax ou o TamMax será maior do que ele. Caso contrário saberemos o TamMax deverá ser menor do que ele.

Uma das soluções para esse problema é o uso de uma busca binária para sortearmos esse número Y, que resulta numa solução de complexidade log(N) para esse problema.

Testes

Entrada

/* Colocarei entradas aqui assim que o bombonera voltar a funcionar */

Saída

/* Colocarei saídas aqui assim que o bombonera voltar a funcionar */

Enquete

Qualidade do enunciado

Dificuldade do problema

Problema interessante

Discuta o problema