Obi 2007 Nível1 Fase2 - Metro

Autora da análise: arianehaselmannarianehaselmann

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

Add a New Comment
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License