Epic battle P77643

L’Ángel i el Darío estan a punt d’enfrontar-se a l’Age of Empires en una batalla È-P-I-C-A. Com que els dos són molt “mancos”, cadascun dels seus soldats escull un soldat enemic a l’atzar i l’ataca. Cada soldat té dos paràmetres, vida i atac, i quan x ataca a y, a la vida de y se li resta l’atac de x. Els soldats moren quan queden amb vida zero o inferior. Suposant que els soldats de l’Ángel atacaran primer, i tots alhora, quin és el nombre esperat de soldats del Darío que moriran?

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb n, el nombre de soldats de l’Ángel, i m, el nombre de soldats del Darío. Segueix la vida i atac dels n jugadors de l’Ángel, i la vida i atac dels m jugadors del Darío. Tots els nombres són naturals entre 1 i 1000.

Sortida

Per a cada cas, escriviu amb quatre decimals el nombre esperat de soldats del Darío que moriran. Els casos de l’entrada no tenen problemes de precisió.

Pista

La solució esperada és una programació dinàmica que té en compte que “l’esperança de la suma és la suma de les esperances”.