No.1280 Beyond C
Problem Statement
A has $N$ cards and B has $M$ cards. The $i$-th cards have positive integers $a_i, b_i$ written on them, respectively.
Each of them shuffles their own cards and randomly chooses one card.
If the product of the integers written on the two chosen cards exceeds $C$, A wins. Otherwise, B wins.
Find the probability that A wins.
Input
$N\ M\ C$ $a_1\ a_2\ \dots\ a_N$ $b_1\ b_2\ \dots\ b_M$
・All inputs are integers.
・$1 \le N, M \le 10^5$
・$1 \le a_i, b_i \le 10^9$
・$1 \le C \le 10^{18}$
Output
Output the probability that A wins.
The output is judged as correct if its absolute error or relative error is at most $10^{-6}$.
Sample
Sample 1
Input
3 2 10 5 4 3 2 3
Output
0.3333333333
There are $6$ ways to choose the cards in total.
Among them, the following combinations have a product exceeding $10$.
$(a, b) = (5, 3), (4, 3)$
Therefore, the probability that A wins is $\frac{1}{3} = 0.333...$.
Sample 2
Input
3 3 4 1 1 1 5 5 5
Output
1
The product is $5$ for every combination, so A wins.
Sample 3
Input
2 1 10 5 6 2
Output
0.5
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
platinum
leafirby