WC '99 P3 - The Godfather

View as PDF

Submit solution

Points: 5
Time limit: 1.0s
Memory limit: 16M

Problem type
Woburn Challenge 1999

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(-x^2)
  • to calculate the area under f(x) from x = 0 to x = L, L \le 2.0, bound f(x) by a 1 \times L rectangle
  • then randomly pick 30\,000 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] \times [# of points on or under f(x)]/[total # of points]

Hints:

  • 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 \dots 1
  • In Pascal: random will give a random number in the range 0 \dots 1
  • In Turing: rand(f), where f is a real, will assign to f a random number in the range 0 \dots 1

Input Specification

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 Specification

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

Comments


  • 0
    iNeedOnions  commented on April 28, 2024, 3:49 a.m.

    When I test it, there is only one test case showing up but I'm only getting 1/5 points. Where are the other test cases? How do I know what is going wrong?