TopCoder problem "Dragon" used in TCHS SRM 12 (Division I Level Three)



Problem Statement

    

An army of k knights is going to try to kill an evil dragon. The dragon has h heads, and the knights must cut off all his heads one by one to complete their mission. Their fight will go as follows:

First, the dragon will attack the knights as many times as he wants (as long he still has at least one head). Each time the dragon attacks, he will either kill one knight with a probability of probDragon or lose one of his heads otherwise. Of course, the dragon may choose not to attack any knights at all. After these attacks, the dragon will return to his cave, and the knights will attack him one by one. When a knight attacks, he will either cut off one of the dragon's heads with a probability of probKnight or get killed by the dragon otherwise. Each knight only gets one turn, so if he cuts off a head, he can NOT attack the dragon again.

If all the dragon's heads are cut off at any point in the fight, the knights' mission will be successful, and the surviving knights will return home with glory. Otherwise, the knights will all be dead and the dragon will still have at least one head on his wide shoulders. Assuming that the dragon acts optimally (tries to maximize the probability of staying alive), return the probability that the knights will complete their mission successfully.

 

Definition

    
Class:Dragon
Method:winFight
Parameters:int, int, int, int
Returns:double
Method signature:double winFight(int h, int k, int probDragon, int probKnight)
(be sure your method is public)
    
 

Notes

-The only thing that matters to the dragon is staying alive. The number of heads left (or the number of knights alive in case of his death) doesn't matter to him.
-The returned value must be accurate to within a relative or absolute value of 1e-9.
 

Constraints

-k will be between 1 and 100, inclusive.
-h will be between 1 and 100, inclusive.
-probDragon will be between 0 and 100, inclusive.
-probKnight will be between 0 and 100, inclusive.
 

Examples

0)
    
1
1
50
50
Returns: 0.5
1)
    
1
10
99
50
Returns: 0.09561792499119559
The optimal strategy for the dragon is to attack until all the knights are killed (or until he is killed).
2)
    
1
5
50
99
Returns: 0.96875
Here, the dragon must follow the same strategy as above, but his chances are much lower.
3)
    
5
4
5
95
Returns: 0.0
The knights can not complete the mission here.
4)
    
2
2
0
25
Returns: 0.0625

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6694

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10064&pm=6694

Writer:

Olexiy

Testers:

PabloGilberto , brett1479 , Cosmin.ro

Problem categories:

Dynamic Programming, Simple Math