Submission #5374954
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[2][201][101][101];
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;
int cur = 0;
int next = 1;
REP(i, 0, n) {
REP(j, 0, 199) {
REP(k, 0, 100) {
REP(l, 0, 100) {
// 1
dp[next][j][k][l] += dp[cur][j][k][l] * 1 / 6.0;
// 2
dp[next][j+1][k][l] += dp[cur][j][k][l] * 1 / 6.0;
// 3
dp[next][j][k+1][l] += dp[cur][j][k][l] * 1 / 6.0;
// 4
dp[next][j+2][k][l] += dp[cur][j][k][l] * 1 / 6.0;
// 5
dp[next][j][k][l+1] += dp[cur][j][k][l] * 1 / 6.0;
// 6
dp[next][j+1][k+1][l] += dp[cur][j][k][l] * 1 / 6.0;
}
}
}
swap(cur, next);
}
double ans = 0;
REP(j, fac[2], 201) {
REP(k, fac[3], 101) {
REP(l, fac[5], 101) {
ans += dp[cur][j][k][l];
}
}
}
cout << ans << endl;
}
Submission Info
Submission Time |
|
Task |
D - サイコロ |
User |
longtime |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
1710 Byte |
Status |
WA |
Exec Time |
2104 ms |
Memory |
32256 KB |
Judge Result
Set Name |
All |
Score / Max Score |
0 / 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 |
1012 ms |
32256 KB |
01 |
TLE |
2104 ms |
32256 KB |
02 |
TLE |
2104 ms |
32256 KB |
03 |
WA |
1137 ms |
32256 KB |
04 |
WA |
1106 ms |
32256 KB |
05 |
TLE |
2104 ms |
32256 KB |
06 |
TLE |
2104 ms |
32256 KB |
07 |
TLE |
2104 ms |
32256 KB |
08 |
AC |
543 ms |
32256 KB |
09 |
TLE |
2104 ms |
32256 KB |
10 |
AC |
1 ms |
256 KB |
90 |
AC |
77 ms |
32256 KB |
91 |
WA |
108 ms |
32256 KB |