Submission #97420


Source Code Expand

#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <ctime>
#include <iterator>
#include <bitset>
#include <numeric>
#include <list>
#include <iomanip>
using namespace std;


typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;

typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;

#define VV(T) vector<vector< T > >

template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
	v.assign(a, vector<T>(b, t));
}

template <class F, class T>
void convert(const F &f, T &t){
	stringstream ss;
	ss << f;
	ss >> t;
}


#define REP(i,n) for(int i=0;i<int(n);++i)
#define ALL(v) (v).begin(),(v).end()
#define RALL(v) (v).rbegin(),(v).rend()
#define PB push_back


#define MOD 1000000009LL
#define EPS 1e-8


int tbl[] = {2, 3, 5};
int add[6][3] = {
	{0, 0, 0},
	{1, 0, 0},
	{0, 1, 0},
	{2, 0, 0},
	{0, 0, 1},
	{1, 1, 0},
};

double dp1[70][70][70];
double dp2[70][70][70];


int main(){
	int cnt[3] = {};
	int n;
	LL d;

	cin >> n >> d;
	LL x = d;
	for(int i = 0; i < 3; ++i){
		while(x % tbl[i] == 0){
			x /= tbl[i];
			++cnt[i];
		}
	}
	if(x != 1){
		puts("0");
		return 0;
	}

	dp1[0][0][0] = 1.0;
	for(int i = 0; i < n; ++i){
		for(int a = cnt[0]; a >= 0; --a)
		for(int b = cnt[1]; b >= 0; --b)
		for(int c = cnt[2]; c >= 0; --c){
		double pr = dp1[a][b][c] / 6.0;
			for(int j = 0; j < 6; ++j){
				dp2	[min(cnt[0], a + add[j][0])]
					[min(cnt[1], b + add[j][1])]
					[min(cnt[2], c + add[j][2])] += pr;
			}
		}
		
		memcpy(dp1, dp2, sizeof(dp1));
		memset(dp2, 0, sizeof(dp2));
	}
	
	printf("%.9f\n", dp1[cnt[0]][cnt[1]][cnt[2]]);
}

Submission Info

Submission Time
Task D - サイコロ
User climpet
Language C++ (G++ 4.6.4)
Score 4
Code Size 2134 Byte
Status AC
Exec Time 184 ms
Memory 6196 KB

Judge Result

Set Name All
Score / Max Score 4 / 4
Status
AC × 13
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 82 ms 6064 KB
01 AC 174 ms 6024 KB
02 AC 156 ms 6064 KB
03 AC 90 ms 6060 KB
04 AC 111 ms 6068 KB
05 AC 184 ms 6068 KB
06 AC 170 ms 6196 KB
07 AC 174 ms 6064 KB
08 AC 59 ms 6064 KB
09 AC 176 ms 6064 KB
10 AC 19 ms 776 KB
90 AC 34 ms 6068 KB
91 AC 35 ms 6076 KB