시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2.5 초 | 512 MB | 3 | 2 | 2 | 66.667% |
You insert $N$ random elements with real-valued keys into a treap. Compute the probability that the height of the treap becomes $h$ ($h = 0, 1, \ldots, N-1$).
A treap is a randomized binary search tree. Each node has a key and a priority. In this problem, assume that both values are real values between 0 and 1. In a treap, the following two conditions are always satisfied:
The following figure shows an example of a treap. In each node, the upper half contains the key, and the lower half contains the priority.
When you insert a node with key $x$, do the following:
In the following figures, a node with key 0.5 and priority 0.5 is inserted into the treap shown above.
You choose $N$ keys uniformly at random between 0 and 1, and insert them one by one into an empty treap. For each $h = 0, 1, \ldots, N - 1$, print the probability that the final height of the treap becomes $h$. The real numbers are sufficiently precise, and the probability that two random numbers become the same is zero. The height is defined as the maximum number of edges you must pass through to go from a leaf to the root.
You are given an integer $N$ ($1 \le N \le 3 \cdot 10^4$).
Print $N$ lines. On the $i$-th line, print the probability that the height becomes $i-1$. The absolute error must be at most $10^{-5}$.
1
1.0
2
0.00000 1.00000