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 |
|
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 |