Descrição
Alexey e Boris eram dois agentes da KGB que moravam em Ecaterimburgo nos anos 70. A cidade era um tanto parada, e, como nada acontecia, para não morrerem em tédio os dois agentes decidiram inventar um jogo de dados. Nele cada um deles começa com VA e VB pontos de vida respectivamente. Cada um têm a sua disposição um número de ataques possíveis, e eles se alternam atacando um ao outro. Cada ataque é descrito por uma quantidade de dados. Para saber o dano do ataque rodamos essa quantidade de dados e a soma dos valores é o dano causado.
Para jogar, eles têm disponível dados honestos com número de faces entre 1 e 12. Isso é, se um dado com L faces for jogado ele vai mostrar um valor inteiro entre 1 e L com igual probabilidade e de maneira independente de qualquer outro lançamento no jogo.
Ambos os jogadores conhecem todos os seus ataques e os do seu oponente e escolhem como atacar em cada turno de forma a maximizar a sua própria probabilidade de vitória.
Sua tarefa nesse problema é determinar qual a probabilidade de vitória de cada jogador.
Entrada
A entrada é composta por diversas instâncias e termina com final de arquivo (EOF).
A primeira linha de cada instância contém quatro inteiros, VA , VB , NA e NB . Cada uma das próximas NA linhas descrevem um ataque do Alexey, elas começam com um inteiro D e são seguidas por outros D inteiros L1 , . . . , LD , indicando que nesse ataque Alexey lança D dados, com L1 , L2 , . . . , LD faces. As próximas NB linhas descrevem os ataques do Boris de maneira análoga.
A entrada deve ser lida da entrada padrão.
Saída
Para cada instância, imprima uma linha com um único ponto flutuante arredondado para 3 casas decimais, indicando a probabilidade que o Alexey vença o duelo, sendo que ele que começa
atacando.
A saída deve ser escrita na saída padrão.
Restrições
• 1 ≤ VA , VB ≤ 300
• 1 ≤ NA , NB ≤ 10
• 1 ≤ D ≤ 3
• 1 ≤ Li ≤ 12
| Exemplos de Entrada | Exemplos de Saída |
|---|---|
|
2 12 2 1 |
0.083 |
Efetue Login ou Cadastre-se para submeter uma solução.
Adaptado por Erich Rodrigues | Competição: USP - Seletiva para Maratona de Programação, 2013