MagicalGirl
SRM 533 · 2011-11-22 · by cgy4ever
Problem Statement
You are going to become a Magical Girl. You will start with M Life Points. M is also the maximal number of Life Points you may have. (I.e., if you gain some Life Points and your new total should exceed M, it will just become equal to M.) As soon as your Life Points drop to 0, you die.
Starting from day 1, at the beginning of each day you will lose one Life Point. The only way to gain Life Points is by defeating the evil witches. There are N witches, conveniently numbered 0 through N-1. Each of the witches will only appear once, for one day of your life. If you decide not to fight her, nothing will happen. If you decide to fight her, there are two possible outcomes: If you win, you will gain some Life Points and the witch disappears. If you lose, she will decrease your Life Points to zero and you die immediately. If multiple witches appear on the same day, you have to fight them one at a time: You pick the first witch to fight. If you defeat her, you gain the corresponding Life Points. Then you pick the second witch to fight, and so on, until you either defeat all the available witches or decide that you do not wish to fight any of the remaining ones.
You are given the
Notes
- On each day, you first lose one Life Point, and only then are you allowed to fight the witches who appear on that day.
- The returned value must be accurate to within a relative or absolute error of 1e-9.
Constraints
- N will be between 1 and 50, inclusive.
- M will be between 2 and 100,000, inclusive.
- day, win and gain will each contain exactly N elements.
- Each element of day will be between 1 and 5,000,000, inclusive.
- Each element of win will be between 0 and 100, inclusive.
- Each element of gain will be between 1 and M, inclusive.
2
{1}
{75}
{1}
Returns: 2.5
Your life would look as follows: You start with 2 Life Points. Day 1 starts, you lose 1 Life Point and you have 1 Life Point left. Then a witch appears. You have a 75% probability of defeating her. If you decide NOT to fight her, you will die on day 2. Here is what would happen if you DO fight her: With probability 0.75, you will win and gain one more Life Point. You would then die on day 3. With probability 0.25, you will die immediately, i.e., on day 1. So if you decide to fight the witch, the expected day of your death is 0.75*3 + 0.25*1 = 2.5. It is therefore a better strategy to fight the witch, and 2.5 is the correct answer.
10
{5,5,5,5}
{100,100,100,100}
{1,1,1,1}
Returns: 14.0
You should fight all the witches since you can always win.
10
{5,5,5,5,5}
{40,80,60,20,0}
{10,10,10,10,10}
Returns: 13.0
It is sufficient to fight a single witch, because the win would already restore your Life Points to M. The best option is to fight the one you are most likely to defeat. Note that fighting her gives you a better expectation than you get from not fighting any witches.
2
{2}
{100}
{2}
Returns: 2.0
On each day, you first lose one Life Point, and only then are you allowed to fight the witches who appear on that day.
20
{2,13,8,7,9,4,6,21}
{18,83,75,23,45,23,10,98}
{10,9,8,10,7,16,13,20}
Returns: 35.908
Submissions are judged against all 133 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class MagicalGirl with a public method double maxExpectation(int M, vector<int> day, vector<int> win, vector<int> gain) · 133 test cases · 2 s / 256 MB per case