Typical DP Contest

Submission #5884601

Source codeソースコード

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

using ll = long long;

int prime[3] = {};  // 2, 3, 5;
double p[100][60][38][26];

double solve(int i, int n2, int n3, int n5) {
    if (p[i][n2][n3][n5] != -1) return p[i][n2][n3][n5];
    if (n2 == 0 && n3 == 0 && n5 == 0) {
        p[i][0][0][0] = 1.0;
        return 1.0;
    }
    if (i < (n2+n3)/2+n5) return 0;
    if (i==0) return 0;
    
    double count = 0;
    count += solve(i-1,max(n2-1,0), n3, n5);  // 2
    count += solve(i-1,n2, max(n3-1,0), n5);  // 3
    count += solve(i-1,n2, n3, max(n5-1,0));  // 5
    count += solve(i-1,max(n2-2, 0),n3,n5); // 4
    count += solve(i-1,max(n2-1, 0),max(n3-1,0),n5); // 6
    count += solve(i-1,n2,n3,n5);  // 1
    p[i][n2][n3][n5] = count / 6.0;
    return p[i][n2][n3][n5];
}

int main(int argc, char *argv[])
{
    int n;
    ll d;
    scanf("%d %lld", &n, &d);
    while(d%2 == 0) {
        prime[0]++;
        d /= 2;
    }
    while(d%3 == 0) {
        prime[1]++;
        d /= 3;
    }
    while(d%5 == 0) {
        prime[2]++;
        d /= 5;
    }
    if (d!=1) {
        printf("0\n");
        return 0;
    }
    for (int i = 0; i < 100; ++i) {
        for (int j = 0; j < 60; ++j) {
            for (int k = 0; k < 38; ++k) {
                for (int l = 0; l < 26; ++l) {
                    p[i][j][k][l] = -1;
                }
            }
        }
    }
    printf("%.15f\n", solve(n, prime[0], prime[1], prime[2]));
    return 0;
}

Submission

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

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

./Main.cpp: In function ‘int main(int, char**)’:
./Main.cpp:35:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %lld", &n, &d);
^

Test case

Set

Set name Score得点 / Max score Cases
All 4 / 4 00,01,02,03,04,05,06,07,08,09,10,90,91

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00 AC 16 ms 46464 KB
01 AC 18 ms 46464 KB
02 AC 17 ms 46464 KB
03 AC 17 ms 46464 KB
04 AC 16 ms 46464 KB
05 AC 19 ms 46464 KB
06 AC 18 ms 46464 KB
07 AC 18 ms 46464 KB
08 AC 16 ms 46464 KB
09 AC 16 ms 46464 KB
10 AC 1 ms 128 KB
90 AC 16 ms 46464 KB
91 AC 16 ms 46464 KB