// the average amount of information in bits obtained in a single query
// version for large sizes
import core.bitop;
import std.algorithm;
import std.math;
import std.range;
import std.stdio;
int n;
int k;
real shannon (R) (R range)
if (is (typeof (range.front) : real))
{
real res = 0.0;
foreach (real element; range)
{
res -= element * log2 (element);
}
return res;
}
void main ()
{
readf (" %s", &n);
assert (1 <= n && n <= 10_000);
readf (" %s", &k);
assert (1 <= k && k <= n);
auto c = new real [] [n + 1];
foreach (i; 0..n + 1)
{
c[i] = new real [i + 1];
c[i][0] = 1.0;
foreach (j; 1..i)
{
c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
}
c[i][i] = 1.0;
}
auto p2 = new real [n + 1];
p2[0] = 1.0;
foreach (i; 1..n + 1)
{
p2[i] = p2[i - 1] * 2.0;
}
real [] p;
for (int v = k; v <= n; v++)
{
p ~= c[v - 1][k - 1] / p2[v];
}
real s = 0.0;
for (int v = 0; v < k; v++)
{
s += c[n][v];
}
s /= p2[n];
p ~= s;
writefln ("%.10g", p.shannon);
}
Ly8gdGhlIGF2ZXJhZ2UgYW1vdW50IG9mIGluZm9ybWF0aW9uIGluIGJpdHMgb2J0YWluZWQgaW4gYSBzaW5nbGUgcXVlcnkKLy8gdmVyc2lvbiBmb3IgbGFyZ2Ugc2l6ZXMKaW1wb3J0IGNvcmUuYml0b3A7CmltcG9ydCBzdGQuYWxnb3JpdGhtOwppbXBvcnQgc3RkLm1hdGg7CmltcG9ydCBzdGQucmFuZ2U7CmltcG9ydCBzdGQuc3RkaW87CgppbnQgbjsKaW50IGs7CgpyZWFsIHNoYW5ub24gKFIpIChSIHJhbmdlKQogICAgaWYgKGlzICh0eXBlb2YgKHJhbmdlLmZyb250KSA6IHJlYWwpKQp7CglyZWFsIHJlcyA9IDAuMDsKCWZvcmVhY2ggKHJlYWwgZWxlbWVudDsgcmFuZ2UpCgl7CgkJcmVzIC09IGVsZW1lbnQgKiBsb2cyIChlbGVtZW50KTsKCX0KCXJldHVybiByZXM7Cn0KCnZvaWQgbWFpbiAoKQp7CglyZWFkZiAoIiAlcyIsICZuKTsKCWFzc2VydCAoMSA8PSBuICYmIG4gPD0gMTBfMDAwKTsKCXJlYWRmICgiICVzIiwgJmspOwoJYXNzZXJ0ICgxIDw9IGsgJiYgayA8PSBuKTsKCglhdXRvIGMgPSBuZXcgcmVhbCBbXSBbbiArIDFdOwoJZm9yZWFjaCAoaTsgMC4ubiArIDEpCgl7CgkJY1tpXSA9IG5ldyByZWFsIFtpICsgMV07CgkJY1tpXVswXSA9IDEuMDsKCQlmb3JlYWNoIChqOyAxLi5pKQoJCXsKCQkJY1tpXVtqXSA9IGNbaSAtIDFdW2ogLSAxXSArIGNbaSAtIDFdW2pdOwoJCX0KCQljW2ldW2ldID0gMS4wOwoJfQoKCWF1dG8gcDIgPSBuZXcgcmVhbCBbbiArIDFdOwoJcDJbMF0gPSAxLjA7Cglmb3JlYWNoIChpOyAxLi5uICsgMSkKCXsKCQlwMltpXSA9IHAyW2kgLSAxXSAqIDIuMDsKCX0KCglyZWFsIFtdIHA7Cglmb3IgKGludCB2ID0gazsgdiA8PSBuOyB2KyspCgl7CgkJcCB+PSBjW3YgLSAxXVtrIC0gMV0gLyBwMlt2XTsKCX0KCXJlYWwgcyA9IDAuMDsKCWZvciAoaW50IHYgPSAwOyB2IDwgazsgdisrKQoJewoJCXMgKz0gY1tuXVt2XTsKCX0KCXMgLz0gcDJbbl07CglwIH49IHM7CgoJd3JpdGVmbG4gKCIlLjEwZyIsIHAuc2hhbm5vbik7Cn0K