Typical DP Contest

Submission #5876104

Source codeソースコード

#include <cstdio>
#include <cmath>

const int MAXK = 11;
const int MAXN = 1024;
int k;
int rate[MAXN];
double r[MAXK][MAXN] = {};
double p[MAXN][MAXN] = {};

void solve(int level) {
    for (int i = 0; i < pow(2, k); ++i) {
        // i-th level => 2**i person
        int num = pow(2, level);
        double sump = 0, pp = 0;
        int js = num * (i / num), je = num * (i / num + 1);
        if ((i - js) < num / 2) {
            js += num / 2;
        } else {
            je -= num / 2;
        }
        for(int j = js; j < je; ++j) {
            sump += r[level-1][j];
        }
        for(int j = js; j < je; ++j) {
            pp += p[i][j] * r[level-1][j] / sump;
        }
        r[level][i] = pp * r[level-1][i];
    }
}

int main(int argc, char *argv[])
{
    scanf("%d", &k);
    for (int i = 0; i < pow(2, k); ++i) {
        scanf("%d", &rate[i]);
    }
    for (int i = 0; i < MAXN; ++i) {
        r[0][i] = 1;
    }
    for (int i = 0; i < pow(2, k) - 1; ++i) {
        for (int j = i + 1; j < pow(2, k); ++j) {
            p[i][j] = 1.0 / (1.0 + pow(10, double(rate[j] - rate[i]) / 400.0));
            p[j][i] = 1.0 / (1.0 + pow(10, double(rate[i] - rate[j]) / 400.0));
        }
    }
    for (int i = 1; i < k+1; ++i) {
        solve(i);
    }
    for (int i = 0; i < pow(2, k); ++i) {
        printf("%.9f\n", r[k][i]);
    }
    return 0;
}

Submission

Task問題 C - トーナメント
User nameユーザ名 vintersnow
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 4
Source lengthソースコード長 1420 Byte
File nameファイル名
Exec time実行時間 116 ms
Memory usageメモリ使用量 8576 KB

Compiler messageコンパイルメッセージ

./Main.cpp: In function ‘int main(int, char**)’:
./Main.cpp:34:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &k);
^
./Main.cpp:36:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &rate[i]);
^

Test case

Set

Set name Score得点 / Max score Cases
All 4 / 4 00,01,02,03,90,91

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00 AC 116 ms 8576 KB
01 AC 114 ms 8448 KB
02 AC 53 ms 8448 KB
03 AC 115 ms 8448 KB
90 AC 1 ms 128 KB
91 AC 1 ms 256 KB