PBG
SRM 768 · 2019-10-09 · by Errichto
Problem Statement
PBG is a shooter game for bears. The next round of this game will involve P polar bears (including Limak), B brown bears and G grizzly bears. We will use N to denote the total number of bears, that is, N = P + B + G.
The PBG game is played in rounds. In each round, a pair of bears is chosen uniformly at random. The two chosen bears fight each other. The loser of the fight is eliminated from the game, the winner remains.
The three bear species can be ordered by strength. Grizzly bears are the strongest, polar bears are in the middle, and brown bears are the weakest. A bear from a stronger species will always beat a bear of a weaker species in a fight. Whenever two bears of the same species fight, each of them has a 50 percent chance to win the fight.
The game ends when there is only one bear left. After the game, each bear is assigned a place: the winner's place is 1 and the other bears are on places 2 to N in reversed elimination order. (That is, the bear that lost the very last fight is in place 2, and the bear that got eliminated first is in place N.)
Limak is one of the polar bears in the game. Find the expected value of his place in the game. Express this value as a reduced fraction X/Y. Return the value X*Y^(-1) modulo 1000000007.
Notes
- Given the constraints used in this problem, if Limak's expected place is a reduced fraction is X/Y, the number Y will never be divisible by (10^9 + 7) = 1,000,000,007.
- The notation Y^(-1) represents the inverse element to Y modulo 10^9 + 7. The previous note implies that this value always exists.
Constraints
- P will be between 1 and 2000, inclusive.
- B will be between 0 and 2000, inclusive.
- G will be between 0 and 2000, inclusive.
5 0 0 Returns: 3
There are five polar bears and each of them is equally likely to take any place from 1 to 5. The expected value of Limak's place is (1+2+3+4+5)/5 = 3.
1 1 1 Returns: 333333338
There is one bear of each species. There are three possibilities: In the first round Limak (a polar bear) meets a brown bear. Since polar bears are a stronger species, Limak wins. In the second round he will then lose to the grizzly bear. Limak's place: 2. In the first round Limak meets the grizzly bear and loses. Limak's place: 3. In the first round the other two bears fight. The grizzly wins. In the second round the grizzly defeats Limak as well. Limak's place: 2. Each of the three scenarios is equally likely, so the answer is (2 + 3 + 2) / 3 = 7 / 3. The correct return value is therefore (7 * 3^(-1)) mod (10^9 + 7) = (7 * 333,333,336) mod (10^9 + 7) = 333,333,338.
1 3 0 Returns: 1
There is one polar bear (Limak) and three brown bears. Limak is the strongest of the four bears, so he will always get first place.
2 3 4 Returns: 672193888
1 0 3 Returns: 333333339
Submissions are judged against all 54 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class PBG with a public method int findEV(int P, int B, int G) · 54 test cases · 2 s / 256 MB per case