Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3307
Magic Machine

Time Limit: 3 Seconds      Memory Limit: 32768 KB

In order to celebrate the 8th anniversary of ZOJ, ZJU ACM coach CYJJ buys a magic machine. But now she has some difficulties with it T_T.

At first, let me show you how the magic machine works:

The input data for the machine is a sequence of n positive numbers. After reading all the data in, it will return a number which is considered to be magic. A number is magic if and only if it appears in the input sequence and its value is the Kth smallest one in the value set of the input. For example, if the numbers are 1 1 1 2, then the 2nd smallest is 2.

Furthermore, we have known the algorithm about how the machine calculates its answer. Let's consider each input a "query interval" (then original input can be considered a interval[1, n]). The magic machine will just work like this:

		ele process(left, right, ele seq[]) {
			if(interval[left, right] is illegal or empty)
				return a number that never appear in the input data;
			else {
				random choose one position i that left <= i <= right {
					the chance of returning the number seq[i] is a;
					the chance of returning the answer for process(left, i - 1, seq) is b;
					the chance of returning the answer for process(i + 1, right, seq) is 1 - a - b;

CYJJ wants to know the chance to get a magic number for a specific input using her magic machine. Now she turns to you, can you help her?


The input contains multiple test cases, each test case begins with a single integer n(n <= 200) which indicates the size of the input sequence. A negtive n indicates the end of input. Then n positive integers follow to specify the input sequence. The last part of input is a line with one integer K(1 <= K <= n) and two float numbers a and b(0 <= a + b <= 1).


For each test case output the chance CYJJ can get a magic number, exact to three digits to the right of the decimal point.

Sample Input

1 1 0

2 0.3 0.5


Sample Output


Author: HE, Xing
Source: ZOJ 8th Anniversary Contest
Submit    Status