|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||512 MB||10||7||4||100.000%|
Lately, a variety of free-to-play collectible card games have become popular. These card games usually have some collection of n cards that the player wants to collect. The player is first given a starter pack of s cards, which is guaranteed to not contain any duplicates (they are all unique). The player can then start acquiring new card(s) in two different ways:
Stingy Larry plays card games of this type all the time. Larry just got a copy of such a game (and is just about to open his starter pack of s cards), and wants to complete a full collection. Assuming that Larry manages his collection optimally, what is the shortest expected time to complete the collection that he can achieve?
The first line of the input contains a single integer T (1 ≤ T ≤ 10), the number of test cases. The first line of each test case contains four integers n (1 ≤ n ≤ 100), the total number of cards in the collection, s (0 ≤ s ≤ n), the starting number of cards, k (1 ≤ k ≤ 10), the number of cards in a pack, and d (1 ≤ d ≤ 100), the number of cards that must be traded for a new card. The next line of the test case then contains n + 1 space-separated real numbers p0, p1, . . . , pn (0.01 ≤ pi ≤ 1), which represent the probabilities of Larry winning a pack after an hour of play. You may assume the pi’s are nondecreasing.
For each test case, output the shortest expected time for Larry to complete the collection in hours. An answer is considered correct if its absolute or relative error is at most 10−7.
2 1 0 1 1 0.25 1.0 10 2 5 5 0.01 0.1 0.2 0.3 0.4 0.5 0.5 0.5 0.5 0.5 1.0
In the first test case, Larry will need to play an average of four hours to win the single card he needs to complete his collection.