# Conditional probability algorithm problem

Byteasar has just arrived at the Bytetown airport and is waiting for his luggage. There are n people (including Byteasar) who were traveling this plane and each of them is waiting for exactly one suitcase. Suitcases are appearing on the conveyor belt in random order.

The Bytefly airline had been facing a serious problem with luggage handling. Many suitcases had vanished forever. In order to deal with this problem, the airline introduced an innovative system of counting the suitcases, which ensures that each aircraft always gets as much suitcases as it should. Unfortunately, it may still happen that two suitcases will be swapped and each of them will fly with the wrong plane. It was shown that for each piece of luggage, it will be on a flight to the wrong city with the probability p.

There are already k suitcases on the conveyor belt and none of them is the Byteasar's one. What is the probability that the Byteasar's suitcase has not arrived to Bytetown with this plane?

Input

The first and only line of input contains two integers n, k and one real number p (1 <= n <= 1.000.000, 0 <= k <= n, 0 <= p <= 1) denoting respectively the number of passengers, the number of suitcases on the conveyor belt and the probability of misplacing the suitcase. The p number is given with at most nine digits after the decimal point.

Output

Your program should output a single line containing the answer to the task - the probability that the Byteasar's suitcase has not arrived with his plane to Bytetown.

Your score will be considered correct as long as it will be in the range [x - epsilon, x + epsilon] , where x is the exact answer and epsilon = 10^(-8).

Example

For the input data:

2 1 0.5 the correct result is:

0.666666666667

So this is a problem that was given to the contestants of this year's Polish Collegiate Programming Contest during the practice day (non-ranked). This leads me to the belief that it should be really easy to solve but still, I'm struggling with it a fair bit and after asking about it on Stackoverflow, I was redirected here with a remark that it could be easily solved algebraically.

My initial idea was that the inverse of probability would be the total number of suitcases in the "pool" of all the suitcases. Later, we calculate all possible n-element sequences without repetition, then we subtract the sequences in which Buteasar's suitcase already appeared (since we know it didn't) and all the cases in which it will (since we are to calculate the scenario in which it doesn't). We divide it by the total count minus the cases in which it already appeared and we have our answer.

The problem with something like this is that pessimistically, we end up calculating a factorial of something in the order of a million so that's sure to cause a overflow of any data type (you're not allowed any external libraries during the competition).

I also tried simplyfing the calculation using arrays for terms of the factorials but going on about me trying various data structures may not bee too much in a spirit of Math.SE so I'l just say it didn't succeed either.

Could you please help me figure this thing out?

## 1 Answer

This is an exercise in Bayes' theorem. Let $A$ be the event that our hero's suitcase got put on the wrong flight, and $B$ be the event that he observes $k$ of $n$ suitcases, none of which are his. We want to compute $P(A|B)$.

We know that $P(A) = p$. The probability that the first $k$ suitcases he observes are not his, given that his suitcase was on the wrong flight, is $1$, so $P(B|A) = 1$. We know that $P(B) = P(B|A)P(A) + P(B|\neg A)P(\neg A) = p + (1-p)P(B|\neg A)$. But $P(B|\neg A)$ is the probability that, given that our hero's suitcase is among the $n$ on the plane, it is not among the first $k$, which is exactly $\displaystyle \frac{n-k}{n}$.

Hence we have $$P(A|B)= \frac{P(B|A)P(A)}{P(B)} = \frac{p}{p + (1-p)\left(\frac{n-k}{n}\right)}.$$

• Absolutely right you are. Thank you a lot, good sir :) – Straightfw Jan 29 '14 at 20:14