Problem D
Dinner Bet
Cesar and Raul like betting and good food, in no particular order. They want to try out a new fancy restaurant and they decided to make a bet – they are going to play a game and the loser pays for dinner.
They have a box with $N$ balls. Each ball contains a distinct number between $1$ and $N$. Then, the game proceeds with these steps:
-
Initially, each person picks $C$ distinct numbers between $1$ and $N$ and writes them down on a separate card.
-
In each round, $D$ balls are drawn from the box uniformly at random. Cesar and Raul mark the ball numbers that appear on their respective card. The $D$ balls are then returned to the box.
-
The game stops when a player has marked all the numbers he chose. That player is the winner. If both players finish at the same time, it is a draw and they will split the dinner.
They are quite eager to try out this new restaurant and they’re now wondering: how many rounds will the game last until at least one of the players has marked all his numbers?
Task
Given the number $N$ of balls, the number $D$ of balls they draw from the box in each round, the amount $C$ of numbers in their cards and the numbers they wrote down, find the expected number of rounds the game will last.
Input
The first line of the input consists of three space separated integers: $N$, $D$, and $C$. $N$ is the number of balls, $D$ is the number of balls drawn in each round, and $C$ is the cards’ size. Each of the following two lines contains $C$ space separated integers: the numbers Cesar and Raul wrote down, respectively.
Constraints
|
$1$ |
$\leq $ |
$N$ |
$\leq $ |
$50$ |
Number of balls in the box |
|
$1$ |
$\leq $ |
$D$ |
$\leq $ |
$\min (10, N)$ |
Number of balls drawn in each round |
|
$1$ |
$\leq $ |
$C$ |
$\leq $ |
$\min (10, N)$ |
Cards’ size |
Output
The output is the expected number of rounds of the game.
The result will be considered correct as long as the absolute error does not exceed $10^{-3}$.
Explanation for Sample Input 1
There are $2$ balls. Cesar picked number $1$ and Raul picked number $2$. In the first round, either number $1$ or $2$ will be drawn and so one of them wins right away.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 1 1 1 2 |
1.00000000 |
| Sample Input 2 | Sample Output 2 |
|---|---|
30 5 10 2 3 5 7 11 13 17 19 23 29 20 18 16 14 12 10 8 6 4 2 |
13.30378396 |
