PaintballFreeForAll
SRM 819 · 2021-12-02 · by misof
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.
Constraints
- N will be between 1 and 100, inclusive.
- P will be between 5000 and 10000, inclusive.
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
Submissions are judged against all 58 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class PaintballFreeForAll with a public method int winner(int N, int P) · 58 test cases · 2 s / 256 MB per case