Background

Not long ago, Sanguosha launched an event-exclusive general for a "triple-server isomorphic" tournament...

So what is the relationship between this problem and SP Sun Ce?

Problem Description

There are now $4$ types of playing cards: Hearts A, Hearts K, Spades A, Spades K. Little Q currently has $n$ spade cards and $m$ heart cards in hand, among which there are $u$ Spades A and $v$ Hearts A, and the opponent has $k$ cards.

Now Little Q knows that the probability that the opponent’s $i$-th card has rank A is $a_i$. Next, he will repeatedly perform the following operation until his turn ends.

1. If you have at least $1$ Hearts A or Hearts K in hand, then you must discard $1$ heart-suit card uniformly at random, and duel with the opponent.
2. Otherwise, you end your turn.

The duel proceeds as follows:

Starting from the opponent, the two sides alternately perform the following operation:

1. If the player has at least $1$ Hearts A or Spades A in hand, then the player must discard $1$ rank-A card uniformly at random.
2. Otherwise, the player takes $1$ point of damage and this duel ends.

Now you want to know, before your turn ends, how much damage the opponent is expected to take.

Input Format

The first line contains $5$ integers $n,m,u,v,k$.

The second line contains $k$ real numbers, in order $a_1,a_2,\cdots,a_k$.

Output Format

Output one real number in one line, representing the expected damage.

This problem uses Special Judge. As long as the absolute error between your answer and the standard output is within $10^{-6}$, your answer will be judged correct.

2 2 1 1 2
0.2 0.8

1.670000000

Hint

Sample Explanation

We can derive that the probabilities that the opponent has $0,1,2$ A cards are $0.16,0.68,0.16$, respectively.

When the opponent has $0$ A cards, no matter which red card Little Q spends each time, he can deal damage to the opponent, so the expected damage in this case is $0.16*2=0.32$.

When the opponent has $1$ A card, suppose Little Q spends an A to duel the first time. After the opponent plays an A, Little Q will play a Spades A, and when the opponent has no A left, the opponent will take damage. Little Q’s other Hearts K can still be spent to duel and deal damage to the opponent, so the expected damage in this case is $0.68*0.5*2=0.68$.

When the opponent has $1$ A card, suppose Little Q spends a K to duel the first time. After the opponent plays an A, Little Q has equal probability to play a Spades A or a Hearts A, and then the opponent will take damage when they have no A left. However, if Little Q plays a Hearts A, he cannot duel again, while if he plays a Spades A, the other Hearts A can still be spent to duel and deal damage to the opponent. Therefore, the expected damage in this case is $0.68*0.5*0.5*1+0.68*0.5*0.5*2=0.51$.

When the opponent has $2$ A cards, if Little Q first spends an A to duel, then after the opponent plays an A, Little Q will play a Spades A. After the opponent plays another A, Little Q will take damage. Little Q’s other Hearts K can still be spent to duel and deal damage to the opponent, so the expected damage in this case is $0.16*0.5*1=0.08$.

When the opponent has $2$ A cards, if Little Q first spends a K to duel, then both sides will each play two A cards, and then the enemy takes damage, and Little Q can no longer duel again, so the expected damage in this case is also $0.16*0.5*1=0.08$.

So the opponent’s expected damage is $0.32+0.68+0.51+0.08+0.08=1.67$.

Constraints

This problem uses bundled testing by subtasks, and the score for each subtask is as follows: | Subtask | Range | Score | | :----------: | :----------: | :----------: | | $0$ | $1\le n,m\le 10$ | $30$ | | $1$ | $1\le n,m\le 2000$ | $70$ |

For all testdata, it holds that $1 \leq n,m,k \leq 2000,1\le u<n,1\le v <m$.

Translated by ChatGPT 5