[UVA][機率] 10777 - God! Save me
God! Save me
Input: standard input
Output: standard output
Time Limit: 1 second
Let there be n doors in a mine contained room. If youchoose ith door, it either takes you to asafe place after xi hours or it returns youto the same room after xi hours traveling.What is the expected length of time (in hours, let P)until you can move to the safe place?
Input
The firstline in the input file is an integer representingthe number of test cases. Each of the test cases follows below. Thefirst line of each caseconsists an integer denoting the value of n ( 0 < n < 100 ).Each of the next n lines contains the value of xi, 0 < |xi|< 25 (if positive it takes you out, if negative it returns you)and pi denoting the probability to choose theith door. You can assume that the sum of all pi equals 1. There may be arbitrary number of spacesbetween the values.
Output
Foreach test case, first print the serial number of the case, a colon, anspace and then print "God! Save me" (without the quotes)if you can't expect to be in the safe place, else print the value of Pcorrected to two digits after decimal point.Check the sample input & output.
Sample Input
2
3
2 0.33
-3 0.33
-5 0.34
3
2 0.34
-3 0.33
-5 0.33
SampleOutput
Case 1: 10.15
Case 2: 9.76
Problem setter: Anupam Bhattacharjee, CSE, BUETThanks to Robin for the alternate solution.
"~~ What Iwant, I find them mistakenly. I don't want what I find ~~"
假如有 1/5 的機率選到正確的門，那麼期望值是 5 次選到正確的門。
假如有 p 的機率選到正確的門，那麼期望值是 1/p 次選到正確的門。
一次罰分的期望值是 sigma(pi*ti)，而選對門的機率是 p
那麼期望值是 sigma(pi*ti)/p。
原本想說會不會替除掉上次錯誤的門，結果還是會選到重覆的門去。
#include <stdio.h>
#include <math.h>
int main() {
int testcase, cases = 0;
int n, i, j;
double x, y;
scanf("%d", &testcase);
while(testcase--) {
scanf("%d", &n);
double p = 1, e = 0;
for(i = 0; i < n; i++) {
scanf("%lf %lf", &x, &y);
if(x > 0)
e += x*y;
else {
e += (-x)*y;
p -= y;
}
}
printf("Case %d: ", ++cases);
if(fabs(p) < 1e-8)
puts("God! Save me");
else
printf("%.2lf\n", e/p);
}
return 0;
}