import java.io.OutputStream; import java.io.IOException; import java.io.InputStream; import java.io.OutputStream; import java.io.PrintWriter; import java.util.Arrays; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; import java.io.Writer; import java.io.OutputStreamWriter; import java.io.BufferedReader; import java.io.InputStream; /** * Built using CHelper plug-in * Actual solution is at the top * * @author lewin */ public class game_show_elimination_lewin { public static void main(String[] args) { InputStream inputStream = System.in; OutputStream outputStream = System.out; InputReader2 in = new InputReader2(inputStream); OutputWriter out = new OutputWriter(outputStream); GameShowElimination solver = new GameShowElimination(); solver.solve(1, in, out); out.close(); } static class GameShowElimination { int n; int k; double[][][] dp; double[][][] prob_elim; double[][] prob; double[][][] prob_reach; double[] ans; void update(int cpos, int j) { int same = cpos >= j && cpos < j + k ? 1 : 0; int above = Math.min(k, Math.max(j + k - cpos - 1, 0)); int below = k - same - above; for (int oi = 1; oi >= 0; oi--) { for (int oj = k; oj >= 0; oj--) { prob[oi][oj] *= 1.0 * below / k; if (oi > 0) prob[oi][oj] += prob[oi - 1][oj] * above / k; if (oj > 0) prob[oi][oj] += prob[oi][oj - 1] * same / k; } } } double extract_prob() { double res = 0; for (int i = 0; i < 2; i++) { for (int j = 0; j <= k; j++) { if (i == 0 && j == 0) continue; res += prob[i][j] / (j + 1) / k; } } return res; } void get_prob_elim(int mask, int above) { // returns probability index i is eliminated for (int i = 0; i < k; i++) { if ((mask & (1 << i)) != 0) { for (int offset = 0; offset < k; offset++) { AUtils.deepFill(prob, 0); prob[0][0] = 1; for (int j = 0; j < k; j++) { if ((i != j) && ((mask & (1 << j)) != 0)) { update(i + offset, j); } } update(i + offset, above); prob_elim[mask][above][i] += extract_prob(); } } } for (int offset = 0; offset < k; offset++) { AUtils.deepFill(prob, 0); prob[0][0] = 1; for (int i = 0; i < k; i++) { if ((mask & (1 << i)) != 0) { update(above + offset, i); } } prob_elim[mask][above][k] += extract_prob(); } } int get_high(int mask) { return mask == 0 ? -1 : Integer.numberOfTrailingZeros(Integer.highestOneBit(mask)); } int[] get_next(int below, int mask, int above) { int nmask = mask; int nbelow = below, nabove = above; int nhigh = get_high(nmask); nabove = Math.min(nabove, nhigh + k); int shift = Math.min(nbelow, k - 1 - nhigh); nbelow -= shift; nabove += shift; nmask <<= shift; nmask += (1 << shift) - 1; return new int[]{nbelow, nmask, nabove}; } void reach(int below, int midmask, int above) { int highest = get_high(midmask); if (above > highest + k) return; double[] probs = prob_elim[midmask][above]; for (int i = 0; i < k; i++) { if (probs[i] > 0) { int[] t = get_next(below, midmask ^ (1 << i), above); prob_reach[t[0]][t[1]][t[2]] += probs[i] * prob_reach[below][midmask][above]; } } if (probs[k] > 0) { int[] t = get_next(below, midmask ^ (1 << highest), highest); prob_reach[t[0]][t[1]][t[2]] += probs[k] * prob_reach[below][midmask][above]; } } double solve(int below, int midmask, int above) { // state looks like |1...below|midmask|above people who are eliminated|highest non eliminated person| // we return expected rank of top player int highest = get_high(midmask); above = Math.min(above, highest + k); if (dp[below][midmask][above] != -1) return dp[below][midmask][above]; if (below == 0 && midmask == 0) { return dp[below][midmask][above] = 1; } double[] probs = prob_elim[midmask][above]; int crank = (below + Integer.bitCount(midmask) + 1); double res = 0; for (int i = 0; i < k; i++) { if (probs[i] > 0) { int[] t = get_next(below, midmask ^ (1 << i), above); res += solve(t[0], t[1], t[2]) * probs[i]; ans[below + i] += probs[i] * crank * prob_reach[below][midmask][above]; } } if (probs[k] > 0) { int[] t = get_next(below, midmask ^ (1 << highest), highest); res += probs[k] * crank; ans[below + highest] += solve(t[0], t[1], t[2]) * probs[k] * prob_reach[below][midmask][above]; } return dp[below][midmask][above] = res; } public void solve(int testNumber, InputReader2 in, OutputWriter out) { n = in.nextInt(); k = in.nextInt(); int top = Math.min(n, k + 1); dp = new double[n + 1][1 << k][2 * k + 1]; AUtils.deepFill(dp, -1); prob = new double[2][k + 1]; prob_elim = new double[1 << k][2 * k + 1][k + 1]; for (int i = 0; i < 1 << k; i++) { for (int j = 0; j < 2 * k + 1; j++) { if (j <= get_high(i) + k) get_prob_elim(i, j); } } prob_reach = new double[n + 1][1 << k][2 * k + 1]; int ibelow = n - top, imask = (1 << (top - 1)) - 1, iabove = top - 1; prob_reach[ibelow][imask][iabove] = 1; for (int below = ibelow; below >= 0; below--) { for (int mask = (1 << k) - 1; mask >= 0; mask--) { for (int above = 0; above <= 2 * k; above++) { if (prob_reach[below][mask][above] > 0) reach(below, mask, above); } } } ans = new double[n]; ans[n - 1] = solve(n - top, (1 << (top - 1)) - 1, top - 1); for (int i = 0; i < n; i++) { out.printf("%.8f\n", ans[i]); } } } static class InputReader2 { private BufferedReader in; private StringTokenizer st; public InputReader2(InputStream stream) { in = new BufferedReader(new InputStreamReader(stream)); st = null; } public int nextInt() { return Integer.parseInt(next()); } public String next() { while (st == null || !st.hasMoreTokens()) { try { st = new StringTokenizer(in.readLine()); } catch (IOException e) { e.printStackTrace(); } } return st.nextToken(); } } static class OutputWriter { private final PrintWriter writer; public OutputWriter(OutputStream outputStream) { writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream))); } public OutputWriter(Writer writer) { this.writer = new PrintWriter(writer); } public void printf(String format, Object... objects) { writer.printf(format, objects); } public void close() { writer.close(); } } static class AUtils { public static void deepFill(double[][][] x, double val) { for (double[][] y : x) deepFill(y, val); } public static void deepFill(double[][] x, double val) { for (double[] y : x) deepFill(y, val); } public static void deepFill(double[] x, double val) { Arrays.fill(x, val); } } }