1557 - Confession

Time Limit : 1 Second

Memory Limit : 128 MB

Submission: 116

Solved: 42


There are N boys and M girls in our school (Huazhong University of  Science and Technology), the boys are labeled

from 1 to N, and the girls are labeled from 1 to M. Every boy has exactly one girl that he loves. For some reason, these

N boys start to confess to the girls they love in the order from 1 to N. 


When a boy confesses to a girl:

if the girl has not accepted a boy yet, then he will have her acceptance with a probability P, otherwise his confession fails.

The boys perform their confession in the order from 1 to N, until boy N has completed his confession.


Given N, M, P and the girl each boy loves, you are asked to answer in average how many boys will get a girl friend.


There are multiple cases, the first line is an integer T, indicating the number of test cases.

For each case:

the first line is two integers N, M and a real number P. (1 <= N, M <= 1000, 0.0 <= P <= 1.0)

the second line is N numbers, each number is in the rang [1, M], indicating the girl each boy loves.

For each test case, output the expected number of boys who get a girl friend. Express the answer rounded to three digits after decimal points.

sample input
2 1 0.61
1 1
3 3 1.0
1 2 3
sample output
Important! To avoid the problem of precision, you should add your answer with 1e-7, for example, if your answer is X, just output it with the following sentence:
printf("%.3lf\n", X + 1e-7);
The 6th ACM Programming Contest of HUST
© 2015 HUST ACMICPC TEAM. All Right Reserved.