1557  Confession
Time Limit : 1 Second
Memory Limit : 128 MB
Submission: 116
Solved: 42
 Description
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.
 Input
 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.
 Output
 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 2 1 0.61 1 1 3 3 1.0 1 2 3
 sample output

0.848 3.000
 hint
 Important! To avoid the problem of precision, you should add your answer with 1e7, for example, if your answer is X, just output it with the following sentence:
printf("%.3lf\n", X + 1e7);  source
 The 6th ACM Programming Contest of HUST