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 1e-7, for example, if your answer is X, just output it with the following sentence:
printf("%.3lf\n", X + 1e-7); - source
- The 6th ACM Programming Contest of HUST