Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

ROBUSMG - Melhorando a robustez de aplicaçőes web

A Web tem crescido a uma taxa assustadoramente alta nos últimos anos, e agora possui mais de 2 bilhões de usuários. Os Web sites mais populares têm milhões de usuários. Devido a esses números, criar uma arquitetura para aplicações Web de larga escala, capazes de suportar milhões de usuários concorrentemente, é uma tarefa difícil, mas importante. Por exemplo, duas preocupações que um projetista tem que ter em mente são a latência (tempo de resposta) e a robustez do sistema.

Aqui, vamos nos preocupar com a robustez. Idealmente, uma aplicação Web deve ficar disponível 100% do tempo. Na prática, servidores falham, e é impossível criar uma arquitetura na qual haja uma garantia de uptime de 100%. Porém, é possível chegar arbitrariamente perto disso. Uma aplicação Web é normalmente estruturada em camadas. Cada camada possui alguma responsabilidade específica, e se comunica com as camadas adjacentes. A figura abaixo mostra um exemplo de arquitetura com 5 camadas:

Note que a arquitetura mostrada na figura possui problemas em potencial de robustez. Há apenas um servidor de aplicação. Se ele falhar, então o sistema não será capaz de atender nenhuma requisição que não possa ser servida diretamente do cache na camada 2. Uma maneira de contornar esse problema é adicionar um segundo servidor de aplicação. Assim, mesmo que um deles falhe, ainda seria possível atender as requisições. Há, claro, a chance de que os dois servidores falhem ao mesmo tempo, mas ela é menor que a chance de que um único servidor falhe isoladamente. O mesmo vale para as outras camadas: é sempre possível adicionar mais servidores e melhorar a robustez daquela camada.

O problema, obviamente, é que servidores extras incorrem em custos extras. Os servidores em si possuem um custo alto, e ainda há o custo de manutenção e energia. Assim, ainda que ter, digamos, 400 servidores de aplicação pudesse aumentar muito a robustez do sistema, essa não seria uma solução interessante devido ao custo.

A probabilidade de falha da i-ésima camada, denotada por pi, é definida como a probabilidade de que todos os servidores naquela camada falhem simultaneamente. Se a probabilidade de falha de um servidor individual naquela camada é f e há n servidores naquela camada, então

pi = fn

A robustez da camada i, denotada por ri, é a probabilidade de que a camada i funcione, e é definida como

ri = 1 - pi = 1 - fn

A robustez do sistema como um todo, denotada por R, é definida como a probabilidade de que todas as camadas do sistema funcionem, simultaneamente:

R = Πi ri

Todos os servidores em uma mesma camada são idênticos. Em particular, eles possuem o mesmo custo, e a mesma probabilidade de falha. Porém, servidores de camadas diferentes podem ser diferentes.

São dados:

  • o número de camadas N do sistema;
  • o custo ci de um servidor da i-ésima camada;
  • a probabilidade de falha fi de um servidor da i-ésima camada e
  • o custo total máximo B.

Você deve determinar qual é a robustez máxima para o sistema como um todo (R) que é possível obter de forma tal que o custo não ultrapasse B.

Observações

Se uma camada tem zero servidores, então sua robustez é zero.

Entrada

Há vários casos de teste.

Cada caso de teste começa com uma linha contendo dois inteiros N e B, respectivamente o número de camadas no sistema (1 ≤ N ≤ 100) e o custo total máximo (1 ≤ B ≤ 1000) em milhares de reais. Em seguida, há N linhas. A i-ésima dessas linhas possui dois números, ci e fi. ci é um inteiro que representa o custo de um servidor na i-ésima camada em milhares de reais (1 ≤ ci ≤ 200). fi é um número de ponto flutuante que representa a probabilidade de falha de um servidor da i-ésima camada (0 < fi ≤ 1, o número é dado com 3 casas decimais de precisão).

A entrada termina com N=B=0, que não deve ser processado.

Saída

Para cada caso de teste, imprima uma linha contendo um único número, a robustez R máxima que é possível obter para o sistema descrito sem estourar o custo máximo. Esse valor deve ser impresso com 3 casas decimais de precisão.

Exemplos

Entrada:
3 105
30 0.100
15 0.200
20 0.500
0 0

Saída:
0.648

Nesse caso, a melhor opção é comprar um servidor para a primeira camada, dois servidores para a segunda camada e dois servidores para a terceira camada, a um custo total de 30 + 15*2 + 20*2 = 100. A robustez da primeira camada será 1 - 0.11 = 0.9. A da segunda camada será 1 - 0.22 = 0.96 e a da terceira camada será 1 - 0.52 = 0.75. Portanto, a robustez total é de 0.9*0.96 *0.75 = 0.648.


Adicionado por:Wanderley Guimarăes
Data:2012-06-21
Tempo limite:0.5s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:Maratona Mineira 2012

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.