Teste da Árvore de Segmentos
Seu Madruga finalmente arrumou um emprego, é sua grande chance de pagar os 14 meses de aluguel que estão atrasados. Seu cargo é o de cortador de papel e o salário é excelente.
Madruga irá receber $$N$$ tiras retangulares de papel com $$1$$ $$cm$$ de largura e $$C$$ $$cm$$ de comprimento. As tiras devem ser colocadas uma ao lado da outra de forma que suas bases estejam alinhadas. A tarefa de seu Madruga será, com apenas um corte em linha reta, paralelo à base, fazer com que a soma das áreas das tiras cortadas seja igual a $$A$$ $$cm^2$$.
Veja a ilustração abaixo com $$N = 5$$ e as tiras com $$5$$, $$3$$, $$6$$, $$2$$ e $$3$$ $$cm$$ de comprimento, respectivamente, para um $$A = 3$$ $$cm^2$$.
Com um corte feito a uma altura de $$4$$ cm em relação a base, a área resultante, pintada de vermelho, é exatamente igual a $$A$$ $$cm^2$$. Sua tarefa é descobrir essa altura $$H$$ e ajudar Seu Madruga a se manter no emprego.
Entrada
Haverá diversos casos de testes. A primeira linha de cada caso inicia com dois inteiros $$N$$ $$(1 \leq N \leq 10^5)$$ e $$A$$ $$(1 \leq A \leq 10^9)$$. representando, respectivamente, a quantidade de tiras e a área resultante esperada. A próxima linha conterá $$N$$ inteiros, representando o comprimento $$C_i$$ $$(1 \leq C_i \leq 10^4)$$ de cada tira.
A entrada termina quando $$C = A = 0$$, a qual não deve ser processada.
Saída
Para cada caso, exiba uma única linha, a altura $$H$$ do corte que Seu Madruga deve fazer para que a soma da área das tiras cortadas seja igual a $$A$$ $$cm^2$$. Use $$4$$ casas decimais após o ponto.
Exiba “: D“, caso nenhum corte seja necessário, ou “-.-” caso seja impossível.
Exemplos
| ENTRADA | SAÍDA |
| 5 3
5 3 6 2 3 4 14 2 5 2 5 0 0 |
4.0000
: D |
Enviar solução: URI