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)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 */
Discuta o problema