Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

Problem F
Supermean
Time Limit: 2 second

"I have not failed. I've just found 10,000 ways that won't work."

Thomas Edison

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 n - 1 numbers listed in non-decreasing order. Repeat this process on the new list of numbers until you are left with just one number - the supermean. I tried writing a program to do this, but it's too slow. :-( Can you help me?

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;
}