DoubleLive
SRM 727 · 2018-01-10 · by Errichto
Problem Statement
You are playing a computer game. Your army consists of B+H warriors: B bears and H humans. A bear has 2 hit points, and a human has 1 hit point.
There is an enemy archer equipped with T arrows. He shoots them one at a time, each time hitting a random warrior (chosen uniformly at random among your warriors that are still alive). A hit warrior loses 1 hit point, and dies immediately if his hit points become 0.
The strength of your army is defined as the product of three values: bears*humans*warriors. For example, if there are 3 bears and 10 humans still alive, the army strength is 3*10*13=390. It doesn't matter whether some bears are wounded (i.e. they have only 1 hit point).
Find the expected value of the army strength when the enemy archer runs out of arrows. Represent the answer as a reduced fraction P/Q. (That is, P and Q must be relatively prime.) For the constraints specified below Q will never be divisible by 10^9 + 7. Compute and return the value P*Q^{-1} modulo (10^9 + 7).
Constraints
- B will be between 1 and 2000, inclusive.
- H will be between 1 and 2000, inclusive.
- T will be between 0 and 2*B+H, inclusive.
4 3 1 Returns: 571428644
The army consists of 4 bears and 3 humans. The enemy archer shoots 1 arrow. With probability 4/7 the arrow will hit one of the bears. A bear loses 1 hit point but doesn't die. The army strength is 4*3*7=84. With probability 3/7 the arrow will hit one of the humans. A human loses 1 hit point and dies. The army will have 4 bears and 2 humans, with total strength 4*2*6=48. The answer is 4/7 * 84 + 3/7 * 48 = 480/7.
3 10 0 Returns: 390
The enemy archer has no arrows, so your whole army survives. The strength is 3 * 10 * 13 = 390.
1 2 2 Returns: 111111113
The army consists of 1 bear and 2 humans. There will be 2 arrows. With probability 1/3 the first arrow hits the only bear. He loses 1 hit point. Then with probability 1/3 the second arrows hits the same bear and thus he dies. The army strength is 0*2*2=0. With probability 1/3 the first arrow hits the only bear, and then with probability 2/3 the second arrow hits and kills one of two humans. The army strength is 1*1*2=2. With probability 2/3 the first arrow hits and kills one of two humans. Then, 1 bear and 1 human remain. The second arrow will hit and kill the human with probability 1/2, and otherwise it will wound the bear. The army strength will be 1*0*1=0 and 1*1*2=2, respectively. The answer is 1/9 * 0 + 2/9 * 2 + 1/3 * 0 + 1/3 * 2 = 0 + 4/9 + 0 + 2/3 = 10/9.
1 1 1 Returns: 1
1 1 2 Returns: 0
3 10 16 Returns: 0
Everybody will die :(
Submissions are judged against all 37 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class DoubleLive with a public method int findEV(int B, int H, int T) · 37 test cases · 2 s / 256 MB per case