Submission #1627561
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
}
writefln("%.10f", dp[N][TWO][THREE][FIVE]);
}
/// 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 |
0 |
Code Size |
4990 Byte |
Status |
RE |
Exec Time |
107 ms |
Memory |
9212 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 |
2 ms |
380 KB |
01 |
AC |
63 ms |
4860 KB |
02 |
AC |
21 ms |
1404 KB |
03 |
AC |
23 ms |
2044 KB |
04 |
AC |
13 ms |
1532 KB |
05 |
AC |
81 ms |
5372 KB |
06 |
AC |
69 ms |
8188 KB |
07 |
AC |
40 ms |
9212 KB |
08 |
RE |
107 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 |