int goal; int[][] stateValue; boolean isOptimal(int money, int bet, int level) { // bet <= money return stateValue[level][money] == stateValue[level-1][min(goal, money+bet)] + stateValue[level-1][money-bet]; } double[] pref; double upTo(int high) { if(high < pref.length) return pref[high]; return pref[pref.length-1] + high - pref.length + 1; } double getInterval(int low, int high) { return upTo(high) - (low == 0 ? 0. : upTo(low - 1)); } int divCeil(int a, int b) { return (a + b - 1) / b; } public double findProbability(int a, int tmp_b, int k) { goal = tmp_b; double[] ans = new double[goal]; Arrays.fill(ans, 1.); stateValue = new int[k+1][goal+1]; stateValue[0][goal] = 1; int[] spec = {0, goal}; for(int level = 1; level <= k; ++level) { double[] old_ans = ans; pref = old_ans; for(int i = 1; i < pref.length; ++i) pref[i] += pref[i-1]; ans = new double[goal+1]; // compute spec[] int[] old_spec = spec; spec = new int[(1 << level) + 1]; for (int i = 0; i <= (1 << level); ++i) spec[i] = divCeil(goal * i, 1 << level); // System.out.print("spec[] = "); write(spec); // compute stateValue[level][] for (int i = 0; i < (1 << level); ++i) for (int j = spec[i]; j < spec[i + 1]; ++j) stateValue[level][j] = i; stateValue[level][goal] = 1 << level; // main algorithm for (int start = 0; start < (1 << level); ++start) { double so_far = 0; int[] next = new int[(1 << (level - 1)) + 1]; int[] begin = new int[(1 << (level - 1)) + 1]; for (int i = 0; i <= 1 << (level - 1); ++i) { next[i] = old_spec[i]; begin[i] = -1; } for(int from = spec[start]; from < spec[start+1]; ++from) { ans[from] = 0; for (int i = 0; i <= 1 << (level - 1); ++i) { if(begin[i] != -1) { begin[i] = max(from, begin[i]); if(begin[i] >= next[i]) begin[i] = -1; } while ((i == 1 << (level - 1) || next[i] < old_spec[i + 1]) && next[i] <= 2 * from && (next[i] < from || isOptimal(from, next[i] - from, level))) { if(next[i] < from) { ++next[i]; continue; } if(begin[i] == -1) begin[i] = next[i]; ++next[i]; } if(begin[i] != -1) { ans[from] += getInterval(begin[i], next[i]-1); ans[from] += getInterval(2*from-(next[i]-1), 2 * from - begin[i]); } } ans[from] /= 2 * (from + 1); } } ans[goal] = 1; } return ans[a]; }