Problem A
Expect the Expected
Input: Standard Input
Output: Standard Output
Some mathematical
background. This problem asks you to compute the expected value of a
random variable. If you haven't seen those before, the simple definitions are
as follows. A random variable is a variable that can have one of several
values, each with a certain probability. The probabilities of each possible
value are positive and add up to one. The expected value of a random
variable is simply the sum of all its possible values, each multiplied by the
corresponding probability. (There are some more complicated, more general
definitions, but you won't need them now.) For example, the value of a fair,
6-sided die is a random variable that has 6 possible values (from 1 to 6), each
with a probability of
I like to play solitaire. Each
time I play a game, I have probability p of solving it and probability
Here is my plan. Every day, I
will play a game of solitaire. If I win, I'll go to sleep happy until the next day.
If I lose, I'll keep playing until the fraction of games I have won today
becomes larger than p. At this point, I'll declare victory and go to
sleep. As you can see, at the end of each day, I'm guaranteed to always keep my
statistics above the expected
If your intuition is telling you that something here must break, then you are right. I can't keep doing this forever because there is a limit on the number of games I can play in one day. Let's say that I can play at most n games in one day. How many days can I expect to be able to continue with my clever plan before it fails? Note that the answer is always at least 1 because it takes me a whole day of playing to reach a failure.
The first line of input gives the number of cases, N. N test cases follow. Each one is a line containing p (as a fraction) and n.
1 ≤ N ≤ 3000, 0 ≤ p < 1,
The denominator of p will be at most 1000,
1 ≤ n ≤ 100.
For each test case, print a line of the form "Case #x: y", where y is the expected number of days, rounded down to the nearest integer. The answer will always be at most 1000 and will never be within 0.001 of a round-off error case.
Sample Input
Output for Sample Input
4 1/2 1 1/2 2 0/1 10 1/2 3 |
Case #1: 2 Case #2: 2 Case #3: 1 Case #4: 2 |
Problemsetter: Igor Naverniouk
Special thanks: Frank Chu