[UVA][二項式定理][log] 10883 - Supermean
Supermean
Time Limit: 2 second
| "I have not failed. I've just found 10,000 ways that won't work." |
Do you know how to compute the mean (or average) of n numbers?
Well, that's not good enough for me. I want the supermean! "What's a
supermean," you ask? I'll tell you. List the n given numbers in
non-decreasing order. Now compute the average of each pair of adjacent
numbers. This will give you
Input
The first line of input gives the number of cases, N.
N test cases follow. Each one starts with a line containing
n (0<n<=50000). The next line will contain
the n input numbers, each one between -1000 and 1000, in non-decreasing
order.
Output
For each test case, output one line containing "Case #x:"
followed by the supermean, rounded to 3 fractional digits.
| Sample Input | Sample Output |
4 1 10.4 2 1.0 2.2 3 1 2 3 5 1 2 3 4 5 |
Case #1: 10.400 Case #2: 1.600 Case #3: 2.000 Case #4: 3.000 |
Problemsetter: Igor Naverniouk
如 http://www.algorithmist.com/index.php/UVa_10883
supermean = ((n-1)C0 * a1 + (n-1)C1 * a2 + .....+(n-1)Cmid-1 * a mid + ... + (n-1)C0 * an) / 2 ^ (n-1)
優化加一加還是搶不下 rank 1
#include <stdio.h>
#include <math.h>
inline int readchar() {
static const int N = 524288;
static char buf[N];
static char *p = buf, *end = buf;
if(p == end) {
if((end = buf + fread(buf, 1, N, stdin)) == buf) return EOF;
p = buf;
}
return *p++;
}
inline double ReadPoint() {
static char c;
int p = 0;
double t = 1;
while((c = readchar()) >= '0')
t /= 10, p = (p << 3) + (p << 1) + (c-'0');
return (double)p*t;
}
inline int ReadDouble(double *x) {
static char c, neg;
while((c = readchar()) < '-') {if(c == EOF) return EOF;}
if(c == '.') {*x = ReadPoint();return 0;}
neg = (c == '-') ? -1 : 1;
*x = (neg == 1) ? c-'0' : 0;
while((c = readchar()) >= '0')
*x = (*x)*10 + c-'0';
if(c == '.') *x += ReadPoint();
*x *= neg;
return 0;
}
inline int ReadInt(int *x) {
static char c, neg;
while((c = readchar()) < '-') {if(c == EOF) return 0;}
neg = (c == '-') ? -1 : 1;
*x = (neg == 1) ? c-'0' : 0;
while((c = readchar()) >= '0')
*x = (*x << 3) + (*x << 1) + c-'0';
*x *= neg;
return 1;
}
int main() {
int n, i, cases = 0;
double LOG[50001];
for(i = 0; i <= 50000; i++)
LOG[i] = log(i);
ReadInt(&i);
while(ReadInt(&n)) {
double B = 0, S = 0, x;
double N2 = (n-1)*log(2);
for(i = 0; i < n; i++) {
ReadDouble(&x);
S += exp(B-N2)*x;
B = B + LOG[n-1-i] - LOG[i+1];
}
printf("Case #%d: %.3lf\n", ++cases, S);
}
return 0;
}