Submission #1627578


Source Code Expand

import std.algorithm;
import std.array;
import std.conv;
import std.functional;
import std.math;
import std.meta;
import std.range;
import std.stdio;
import std.string;
import std.traits;
import std.typecons;

enum INF(T) = T.max / 2; ///longの場合10^^18くらい

void main()
{
	long N, D;
	readf("%s %s", &N, &D);
	long TWO, THREE, FIVE;
	while (D % 2 == 0)
	{
		D /= 2;
		TWO++;
	}
	while (D % 3 == 0)
	{
		D /= 3;
		THREE++;
	}
	while (D % 5 == 0 && D != 1)
	{
		D /= 5;
		FIVE++;
	}
	if (D != 1)
	{
		writeln(0);
		return;
	}
	auto dp = new double[long][long][long][](N + 1);
	dp[0][0][0][0] = 1;

	foreach (i; 0 .. N)
		foreach (two; dp[i].byKey)
			foreach (three; dp[i][two].byKey)
				foreach (five; dp[i][two][three].byKey)
				{
					dp[i + 1][two][three][five] += dp[i][two][three][five] / 6; // 1
					dp[i + 1][min(two + 1, TWO)][three][five] += dp[i][two][three][five] / 6; // 2
					dp[i + 1][two][min(three + 1, THREE)][five] += dp[i][two][three][five] / 6; // 3
					dp[i + 1][min(two + 2, TWO)][three][five] += dp[i][two][three][five] / 6; // 4
					dp[i + 1][two][three][min(five + 1, FIVE)] += dp[i][two][three][five] / 6; // 5
					dp[i + 1][min(two + 1, TWO)][min(three + 1, THREE)][five] += dp[i][two][three][
					five] / 6; // 6
				}
	if (TWO in dp[N] && THREE in dp[N][TWO] && FIVE in dp[N][TWO][THREE])
		writefln("%.10f", dp[N][TWO][THREE][FIVE]);
	else
		writeln(0);
}

/// graphMatrix[from][to] == cost < INF!T
T[][] graphMatrix(T = long)(size_t e)
{
	auto m = new T[][](e, e);
	foreach (ref r; m)
		r[] = INF!T;
	return m;
}
/// デバッグ用。GraphMatrixを見やすい文字列にする
string fmt(T)(T[][] graph)
{
	auto result = "";
	foreach (r; graph)
	{
		result ~= r.map!(n => (n == INF!T) ? "max" : n.to!string).join("\t") ~ "\n";
	}
	return result;
}

/// warshallFloyd[from][to] == minCost
T[][] warshallFloyd(T)(T[][] graph)
{
	auto result = new T[][](graph.length, graph.length);
	foreach (i, ref r; result)
		r[] = graph[i];

	foreach (relay; 0 .. graph.length)
		foreach (from; 0 .. graph.length)
			foreach (to; 0 .. graph.length)
				result[from][to] = min(result[from][to], result[from][relay] + result[relay][to]);
	return result;
}
/// dijkstra[to] == minCost
T[] dijkstra(T = long)(T[][] graph, size_t from)
{
	auto result = new T[](graph.length);
	result[] = INF!T;
	result[from] = 0;
	auto queue = new bool[](graph.length);
	queue[] = false;
	foreach (_; 0 .. graph.length)
	{
		size_t min = result.maxIndex();
		foreach (i; 0 .. graph.length)
			if (queue[i] == false && result[i] < result[min])
				min = i;
		queue[min] = true;

		foreach (to; 0 .. graph.length)
		{
			if (result[min] + graph[min][to] < result[to])
				result[to] = result[min] + graph[min][to];
		}
	}
	return result;
}

/// dmd-2.070のstd.algorithmにはminIndexがない
size_t minIndex(T)(T[] array)
{
	size_t result;
	T _n = array[0];
	foreach (i, n; array)
		if (n < _n)
			result = i;
	return result;
}
/// dmd-2.070のstd.algorithmにはmaxIndexがない
size_t maxIndex(T)(T[] array)
{
	size_t result;
	T _n = array[0];
	foreach (i, n; array)
		if (_n < n)
			result = i;
	return result;
}

/// 親 = fun(子A, 子B)
template segTree(fun...)
{
	alias binfuns = binaryFun!fun;
	Tuple!(T[], "tree", T[], "data") segTree(T)(T[] data, T default_value)
	{
		immutable new_data_length = cast(size_t)(2 ^^ data.length.log2.ceil());
		immutable tree_length = new_data_length - 1;

		T[] tree = new T[](tree_length + new_data_length);

		tree[tree_length .. tree_length + data.length] = data[];
		tree[tree_length + data.length .. $] = default_value;

		foreach_reverse (depth; 0 .. cast(size_t) data.length.log2.ceil())
			foreach (i; 0 .. 2 ^^ depth)
			{
				immutable parent = 2 ^^ depth - 1 + i;
				tree[parent] = binfuns(tree[(parent + 1) * 2 - 1], tree[(parent + 1) * 2]);
			}
		return Tuple!(T[], "tree", T[], "data")(tree, tree[tree_length .. $]);
	}
}
///デバッグ用
string fmt(T)(Tuple!(T[], "tree", T[], "data") segtree)
{
	string result;
	immutable depth = cast(size_t) segtree.tree.length.log2.ceil();
	foreach (i; 0 .. depth)
		result ~= segtree.tree[2 ^^ i - 1 .. 2 ^^ (i + 1) - 1].map!(to!string)
			.join('\t'.repeat.take(2 ^^ (depth - i - 1)).array.idup) ~ "\n";
	return result;
}
/// target番目のデータをvalueに更新し、それに合わせてsegtreeを更新
template update(fun...)
{
	alias binfuns = binaryFun!fun;
	void update(T)(Tuple!(T[], "tree", T[], "data") segtree, size_t target, T value)
	{
		segtree.data[target] = value;
		size_t parent = (segtree.tree.length - segtree.data.length) + target + 1;
		while (true)
		{
			parent /= 2;
			if (parent == 0)
				return;
			immutable childA = parent * 2;
			immutable childB = childA + 1;
			T newVal = binfuns(segtree.tree[childA - 1], segtree.tree[childB - 1]);
			if (segtree.tree[parent - 1] == newVal)
				return;
			segtree.tree[parent - 1] = newVal;
		}
	}
}

Submission Info

Submission Time
Task D - サイコロ
User kotet
Language D (DMD64 v2.070.1)
Score 4
Code Size 5085 Byte
Status AC
Exec Time 82 ms
Memory 8956 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 3 ms 380 KB
01 AC 64 ms 5244 KB
02 AC 22 ms 1404 KB
03 AC 23 ms 2044 KB
04 AC 13 ms 1532 KB
05 AC 82 ms 5116 KB
06 AC 70 ms 8956 KB
07 AC 41 ms 7804 KB
08 AC 11 ms 1148 KB
09 AC 9 ms 1660 KB
10 AC 1 ms 256 KB
90 AC 1 ms 256 KB
91 AC 1 ms 256 KB