Submission #5375395
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define REP(i,begin, n) for(int i=begin;i<n;i++)
typedef long long int lli;
typedef pair<int, int> P;
map<lli, lli> fac;
// dp[i][j][k][l]: i個目のサイコロを振った時点で2,3,5がそれぞれj,k,l個使われている確率
double dp[101][63][63][63];
int main() {
int n;
lli d;
cin >> n >> d;
while(d%2==0){
d=d/2;
fac[2]++;
}
while(d%3==0){
d=d/3;
fac[3]++;
}
while(d%5==0){
d=d/5;
fac[5]++;
}
if(d!=1){
cout<<0<<endl;
return 0;
}
dp[0][0][0][0] = 1.0;
REP(i, 0, n) {
REP(j, 0, 61) {
REP(k, 0, 61) {
REP(l, 0, 61) {
// 1
dp[i+1][j][k][l] += dp[i][j][k][l] * 1 / 6.0;
// 2
dp[i+1][min(j+1, 60)][k][l] += dp[i][j][k][l] * 1 / 6.0;
// 3
dp[i+1][j][min(k+1, 60)][l] += dp[i][j][k][l] * 1 / 6.0;
// 4
dp[i+1][min(j+2, 60)][k][l] += dp[i][j][k][l] * 1 / 6.0;
// 5
dp[i+1][j][k][min(l+1, 60)] += dp[i][j][k][l] * 1 / 6.0;
// 6
dp[i+1][min(j+1, 60)][min(k+1, 60)][l] += dp[i][j][k][l] * 1 / 6.0;
}
}
}
}
double ans = 0;
REP(j, fac[2], 61) {
REP(k, fac[3], 61) {
REP(l, fac[5], 61) {
ans += dp[n][j][k][l];
}
}
}
cout << ans << endl;
}
Submission Info
Submission Time |
|
Task |
D - サイコロ |
User |
longtime |
Language |
C++14 (GCC 5.4.1) |
Score |
4 |
Code Size |
1674 Byte |
Status |
AC |
Exec Time |
430 ms |
Memory |
176512 KB |
Judge Result
Set Name |
All |
Score / Max Score |
4 / 4 |
Status |
|
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 |
132 ms |
63872 KB |
01 |
AC |
387 ms |
164224 KB |
02 |
AC |
346 ms |
149888 KB |
03 |
AC |
149 ms |
72064 KB |
04 |
AC |
144 ms |
70016 KB |
05 |
AC |
430 ms |
176512 KB |
06 |
AC |
381 ms |
162176 KB |
07 |
AC |
358 ms |
153984 KB |
08 |
AC |
70 ms |
35200 KB |
09 |
AC |
341 ms |
147840 KB |
10 |
AC |
1 ms |
256 KB |
90 |
AC |
10 ms |
4480 KB |
91 |
AC |
14 ms |
6528 KB |