Problem Statement
Time limit is 3 seconds.
N people are going to play a game with paintball weapons.
Initially, all players are active. When there is at most one active person, the game ends.
The game is played in rounds. Only the players who are still active take part in each round.
Each round looks as follows: each active person chooses one of their active opponents (uniformly at random). Then, everyone takes a shot at their chosen opponent. Each shot hits the intended target with probability P/10000 and misses completely otherwise. Everyone who got hit (one or more times) stops being active.
If there is an active person at the end of the game, they are the winner. Calculate the probability with which the game has a winner.
Let A/B be the probability as a reduced fraction. Return (A*inv(B)) modulo M, where M = 10^9 + 7 and inv(x) denotes the inverse of x, modulo M.
Definition
- Class:
- PaintballFreeForAll
- Method:
- winner
- Parameters:
- int, int
- Returns:
- int
- Method signature:
- int winner(int N, int P)
- (be sure your method is public)
Constraints
- N will be between 1 and 100, inclusive.
- P will be between 5000 and 10000, inclusive.
Examples
1
7400
Returns: 1
The game is over immediately. The only player is the winner.
2
7000
Returns: 923076930
In each round the two players shoot each other. With probability 9% both miss, with probability 42% one of them hits, and with probability 49% both hit their target. The exact answer as a fraction is 42/91. We have inv(91) = 164,835,166, and then (42 * 164,835,166) modulo 1,000,000,007 is the answer we should return.
3
10000
Returns: 750000006
Three players, each of them is a perfect marksman. The game always has just a single round. In the first round, with probability 25% they choose their targets so that everyone dies and loses. With probability 75% two of them shoot the same person, that person shoots one of the other two, and there is exactly one survivor who wins. The exact probability of having a winner is 3/4.
5
8000
Returns: 303916351
The exact answer here is 14849540/25494183.
1
10000
Returns: 1
2
10000
Returns: 0
3
7744
Returns: 783921129
100
6895
Returns: 880613418
46
10000
Returns: 152471632
56
9675
Returns: 929145571
44
9197
Returns: 460781124
50
5335
Returns: 833074243
54
10000
Returns: 780539421
14
10000
Returns: 767183826
34
9478
Returns: 564609502
2
9649
Returns: 556178151
55
6947
Returns: 132151076
67
8622
Returns: 745953057
31
10000
Returns: 132186541
72
7895
Returns: 916090837
77
9569
Returns: 500638545
74
6954
Returns: 856533952
5
7735
Returns: 973803498
13
9737
Returns: 523505766
50
5795
Returns: 213024696
84
7743
Returns: 461665487
28
5902
Returns: 198302086
54
7345
Returns: 372787590
31
7924
Returns: 937722297
69
10000
Returns: 773786275
62
9609
Returns: 482071167
51
9254
Returns: 617198875
29
10000
Returns: 128029732
94
8976
Returns: 957544754
95
8636
Returns: 163025980
91
9480
Returns: 672309160
92
10000
Returns: 491389231
95
8568
Returns: 167179807
96
10000
Returns: 868786937
100
9985
Returns: 819321087
99
7580
Returns: 24139039
91
6731
Returns: 940806739
96
6507
Returns: 554589079
93
6627
Returns: 464167748
93
10000
Returns: 905225975
93
9320
Returns: 157158268
97
10000
Returns: 490549931
95
5003
Returns: 447791114
92
5550
Returns: 699040324
96
10000
Returns: 868786937
95
10000
Returns: 72666284
93
9191
Returns: 235273521
98
9052
Returns: 425650720
99
9617
Returns: 795020303
100
10000
Returns: 679818452
92
6233
Returns: 682321347
99
5382
Returns: 38656073
100
5501
Returns: 118062826