Frost Chain
Time Limit: 1.0 Seconds Memory Limit: 65536K
In the unimaginable popular DotA game, the hero Lich has a wonderful skill: Frost
Chain, release a jumping breath of frost that jumps N times against enemy units.
Today iSea play the role of Lich, at first he randomly chooses an enemy hero to
release the skill, then the frost jumps for N times. Each time, it make a damage of one
HP unit on this hero (including the first time), then bounces to another hero (can’t be
himself) if their distance is no more than D and this hero is alive of course, also
randomly. Here random means equal probability.
Now we know there are always only five enemy heroes, and also their coordinates
and HP value. iSea wonders the death probability of each hero. One hero is dead if its
HP is equal to or less than zero.
Input
There are several test cases in the input.
Each test case begin with two integers N and D (1 <= N <= 25, 1 <= D <= 10000).
