Frankfurt UAS Programming Day

#### Start

2018-06-12 10:00 UTC

## Frankfurt UAS Programming Day

#### End

2018-06-12 15:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -310 days 6:47:38

5:00:00

0:00:00

# Problem CDinner 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?

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