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
1
1
50
50
Returns: 0.5
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).
100
100
50
50
Returns: 7.888609052210118E-31
1
5
50
99
Returns: 0.96875
Here, the dragon must follow the same strategy as above, but his chances are much lower.
1
10
50
100
Returns: 0.9990234375
5
4
5
95
Returns: 0.0
The knights can not complete the mission here.
50
100
50
50
Returns: 0.5397946186935894
1
1
30
70
Returns: 0.7
1
1
20
70
Returns: 0.7
1
1
30
80
Returns: 0.7
2
2
0
25
Returns: 0.0625
3
3
0
25
Returns: 0.015625
56
57
59
26
Returns: 7.349924223363407E-32
66
77
30
64
Returns: 1.97320031153974E-5
60
89
21
90
Returns: 0.9999999988673954
39
93
80
43
Returns: 0.004555077015140361
18
63
98
71
Returns: 2.6469625923040198E-14
97
96
40
32
Returns: 0.0
79
99
72
41
Returns: 3.474884429958649E-15
11
57
59
45
Returns: 0.9999877891122695
59
82
38
90
Returns: 0.9999599159911005
58
86
53
52
Returns: 0.0026618960775413106
48
76
53
50
Returns: 0.01431332775436894
12
54
61
4
Returns: 1.1947322642939953E-6
47
52
87
90
Returns: 1.2790794258914473E-17
20
94
88
53
Returns: 0.04736226672110189
72
76
50
100
Returns: 0.3187829131060702
50
89
85
38
Returns: 5.228881974949667E-10
19
68
87
22
Returns: 0.012882161625717974
21
50
25
22
Returns: 0.0012074065654249307
3
27
57
70
Returns: 0.9999777974786386
67
100
72
87
Returns: 2.9787897124406993E-4
67
75
83
70
Returns: 1.5458726724549013E-17
5
49
2
76
Returns: 1.0
85
84
100
84
Returns: 0.0
69
76
87
53
Returns: 7.482538199718134E-25
4
37
66
8
Returns: 0.3432941851345988
40
55
25
68
Returns: 0.2758337185490052
16
76
64
48
Returns: 0.9999617416870157
86
95
46
14
Returns: 1.1347306171984474E-62
42
50
21
48
Returns: 1.4104560442301037E-7
75
94
12
47
Returns: 6.790989902839309E-11
70
87
20
79
Returns: 0.429456602036718
26
85
4
96
Returns: 1.0
7
23
61
2
Returns: 2.3672352314150918E-7
87
97
21
79
Returns: 0.004332376631577603
59
98
51
38
Returns: 7.027860452224717E-6
50
76
76
85
Returns: 3.850879825000564E-5
13
100
46
83
Returns: 1.0
71
69
19
62
Returns: 0.0
64
99
25
47
Returns: 3.0535924615516315E-4
5
55
45
17
Returns: 0.9681115352015662
47
67
100
15
Returns: 0.0
78
83
76
32
Returns: 1.0969895586611272E-32
76
91
94
3
Returns: 6.37480449890708E-100
83
95
85
70
Returns: 2.8894264228804023E-24
43
99
21
25
Returns: 4.823053675430724E-5
51
100
50
100
Returns: 0.999959627799777
51
100
99
100
Returns: 1.117623717981533E-62
7
8
55
50
Returns: 0.03515625
1
1
100
10
Returns: 0.0
2
2
0
25
Returns: 0.0625
100
100
60
34
Returns: 1.405696955498277E-47
4
5
66
50
Returns: 0.17333423467102718
90
100
11
71
Returns: 4.035124878400179E-6
99
99
34
33
Returns: 2.1521872187474537E-48
27
97
79
39
Returns: 0.42589754490202664
100
100
0
0
Returns: 0.0
89
98
43
87
Returns: 0.1653114840475493
26
99
92
13
Returns: 4.604330142993238E-6