Submission #5833775


Source Code Expand

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
 
#define _USE_MATH_DEFINES
#define mp       make_pair
#define pb       push_back
#define fst      first
#define snd      second
#define all(x)   (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

typedef    vector<double>     vb;
typedef    vector<vb>         vvb;
typedef    vector<vvb>        vvvb;
typedef    vector<vvvb>       vvvvb;

const int INF=1<<29;
const double EPS=1e-9;

const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};


int main()
{
    int N; cin >> N;
    long long D; cin >> D;

    int factor[] = {2, 3, 5};
    int factor235[3][6] = {
        {0,1,0,2,0,1},  // 2
        {0,0,1,0,0,1},  // 3
        {0,0,0,0,1,0}   // 5
    };

    // primefac D
    int F[3] = {0};
    rep(i,3) {
        while(D % factor[i] == 0) {
            F[i]++;
            D /= factor[i];
        }
    }

    if(D != 1) {
        printf("%d\n", 0);
        return 0;
    }

    vvvvb dp(N+1, vvvb(F[0]+1, vvb(F[1]+1, vb(F[2]+1, 0))));
    dp[0][0][0][0] = 1;
    int M[3] = {0};
    rep(n,N) {
        for(int i2 = M[0]; i2 >= 0; i2--) {
            for(int i3 = M[1]; i3 >= 0; i3--) {
                for(int i5 = M[1]; i5 >= 0; i5--) {
                    if(dp[n][i2][i3][i5] == 0)
                        continue;

                    rep(i,6) {
                        int n2 = min(i2+factor235[0][i], F[0]);
                        int n3 = min(i3+factor235[1][i], F[1]);
                        int n5 = min(i5+factor235[2][i], F[2]);
                        dp[n+1][n2][n3][n5] += dp[n][i2][i3][i5] / 6;
                        M[0] = max(M[0], n2);
                        M[1] = max(M[1], n3);
                        M[2] = max(M[2], n5);
                    }
                }
            }
        }
    }

    printf("%.9f\n", dp[N][F[0]][F[1]][F[2]]);
    return 0;
}

Submission Info

Submission Time
Task D - サイコロ
User loupbita
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2214 Byte
Status WA
Exec Time 62 ms
Memory 2048 KB

Judge Result

Set Name All
Score / Max Score 0 / 4
Status
AC × 5
WA × 8
Set Name Test Cases
All 00, 01, 02, 03, 04, 05, 06, 07, 08, 09, 10, 90, 91
Case Name Status Exec Time Memory
00 AC 1 ms 256 KB
01 WA 25 ms 1280 KB
02 WA 1 ms 512 KB
03 WA 2 ms 512 KB
04 WA 2 ms 384 KB
05 WA 3 ms 1280 KB
06 WA 62 ms 2048 KB
07 WA 51 ms 2048 KB
08 AC 6 ms 768 KB
09 WA 2 ms 512 KB
10 AC 1 ms 256 KB
90 AC 1 ms 256 KB
91 AC 1 ms 256 KB