MagicBlizzard
SRM 526.5 · 2011-12-12 · by cgy4ever
SRM 526.5 · 2011-12-12 · by cgy4ever · Math, Sorting
Problem Statement
Problem Statement
Today is the Christmas Eve. People around the world celebrate this
holiday. The following story takes place in the land of reindeer, where Santa Claus resides.
For Christmas, the land should be covered by snow, but there was no snowfall yet. Luckily, the reindeer know a spell called Magic Blizzard that can make it snow.
The land can be imagined as an infinite grid of unit squares with integer coordinates. When a reindeer casts Magic Blizzard, the effect depends on two parameters: the range of the spell R and the amount A. The spell will generate A snowballs. Each snowball will fall on some square with coordinates (x,y) such that -R <= x, y <= R. For each snowball, the target square is chosen uniformly at random. Targets for snowballs are chosen independently of each other. (Hence it is possible that multiple snowballs will hit the same square.)
N reindeer are going to cast Magic Blizzard, one after another. You are given twoint[] s range and amount of length N. The spell by reindeer i will have range equal to range[i] and the amount of snowballs it produces will be amount[i].
The beauty of the landscape can be computed as the total beauty of all squares. The beauty of a square that was hit by x snowballs is x^2.
Your method must compute and return the expected value of the beauty of the landscape.
For Christmas, the land should be covered by snow, but there was no snowfall yet. Luckily, the reindeer know a spell called Magic Blizzard that can make it snow.
The land can be imagined as an infinite grid of unit squares with integer coordinates. When a reindeer casts Magic Blizzard, the effect depends on two parameters: the range of the spell R and the amount A. The spell will generate A snowballs. Each snowball will fall on some square with coordinates (x,y) such that -R <= x, y <= R. For each snowball, the target square is chosen uniformly at random. Targets for snowballs are chosen independently of each other. (Hence it is possible that multiple snowballs will hit the same square.)
N reindeer are going to cast Magic Blizzard, one after another. You are given two
The beauty of the landscape can be computed as the total beauty of all squares. The beauty of a square that was hit by x snowballs is x^2.
Your method must compute and return the expected value of the beauty of the landscape.
Notes
- The returned value must be accurate to within a relative or absolute error of 1e-9.
Constraints
- range will contain between 1 and 50 elements, inclusive.
- amount will contain between 1 and 50 elements, inclusive.
- range and amount will contain the same number of elements.
- Each element in range will be between 0 and 10,000, inclusive.
- Each element in amount will be between 1 and 10,000, inclusive.
Examples
0)
{1,0}
{1,1}
Returns: 2.2222222222222223
The second snowball will surely fall on the square (0,0). The first snowball will fall on the same square with probability 1/9. If that happens, the beauty of the landscape will be 2^2 = 4. Otherwise, we will have two squares containing one snowball each, for a total beauty of 1^2 + 1^2 = 2. So the expected beauty is (1/9) * 4 + (8/9) * 2 = 20/9.
1)
{1,0}
{2,1}
Returns: 3.666666666666667
2)
{5,2,6,5}
{1,2,2,3}
Returns: 8.46525111252384
3)
{7,11,2,13,3,19,5,17}
{16,8,4,15,12,9,10,6}
Returns: 98.55659436211914
4)
{0,0,0,0,0,0,0,0,0,0}
{10000,10000,10000,10000,10000,10000,10000,10000,10000,10000}
Returns: 1.0E10
Note that the answer can be very large.
Submissions are judged against all 110 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class MagicBlizzard with a public method double expectation(vector<int> range, vector<int> amount) · 110 test cases · 2 s / 256 MB per case