Woburn Challenge 1999
Godfather
The powerful Carlo crime family was quite unique among villains. In order for the younger generation to participate in the activities of the family, Don Monty Carlo decreed that they must do well in school (just like US College basketball). [For those of you unfamiliar with crime bosses, the Don is the head of the family]. But alas, the future of the Carlo crime family is threatened by the academic incompetence of the eldest son, Carlos, who is failing Law and Ethics. Don Carlo recognizes the futility of trying to get his son to do better in school and so he opts for a more illegal route (just like US College basketball) and decides to manipulate the bell curve of the class. While the exact details of this nefarious plot of coercion and extortion are irrelevant, it suffices to say that he needs to be able to calculate the area under a bell curve. Since Don Monty Carlo wasn't too good at math, he has "hired" a computer programmer and made him an offer he can't refuse. And being a run-of-the-mill narcissistic thug, he has instructed the programmer to use the Monte Carlo method of area calculation (also known as integration). Oh yeah, did we happen to mention that you are the programmer?
The Monte Carlo method works as follows:
- the function to be integrated is f(x) = exp(-x2)
- to calculate the area under f(x) from x=0 to x=L, L ≤ 2.0, bound f(x) by a 1 x L rectangle
- then randomly pick 30000 points inside the rectangle and determine how many of them fall on or under f(x)
- then the area under f(x) = [Area of rectangle x]*[# of points on or under f(x)]/[total # of points]
- For all languages: don't forget to call randomize() at the start of your program.
- In C/C++: (float) rand() / (float) RAND_MAX will give a random number in the range 0..1
- In Pascal: random will give a random number in the range 0..1
- In Turing: rand(f), where f is a real, will assign to f a random number in the range 0..1
Input
A series of test cases; for each test case the value of L is given on a line by itself. The number '-1' denotes the end of the input.Output
Estimate of the area under f(x) from x=0 to x=L (rounded to 2 decimal places); it has to match our answer to within 0.03.Note that we will check the text of your program to ensure that you are in fact using the Monte Carlo method. You don't want to cross the Don.
Sample Input
0.0 -1
Sample Output
0.00
All Submissions
Best Solutions
Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Sep 29, 2008
Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Comments (Search)
Draw the curve y = exp(-x^2). exp(z) represents the function e^z, where e is the base of the natural logarithm.
We would like to know the area bounded above by the curve, below by the x-axis, on the left by the vertical line x = 0, and on the right by the vertical line x = L (where L is the input.) This is similar to how displacement is obtained in physics by finding the area under a v-t graph...
How will you find this area? Choose 30000 random points within a box of height 1 and width L with its lower-left corner at the origin. For each point, determine whether or not it lies on or below the curve. Call the number of such points N...
Then, N/30000 is then the fraction of points that were below the curve. It is therefore reasonable to conclude that the desired area is (N/30000) * [area of rectangle] = NL/30000. (Think about it. If you randomly throw 30000 darts at a dartboard on which the bullseye has 1/100 the area of the whole board, you would expect approximately 300 darts to land in the bullseye.)
You don't need to know if one is inside the other. However, the maximal value of f(x) = e^(-x^2) is achieved when x^2 is as small as possible - zero - and f(x) is then one. Thus the rectangle completely covers a segment of the curve.