from decimal import * getcontext().prec = 30 # let's hope this works test_num, sub_num = [int(i) for i in input().split()] test_num -= 1 # we don't care about the sample comb_vals =  curr = 1 at = test_num for k in range(test_num + 1): comb_vals.append(curr) curr = curr * at // len(comb_vals) at -= 1 pow_ = 2 ** test_num prob = [Decimal(v) / pow_ for v in comb_vals] # this[i] = the change of getting at least i test cases prob_meet = [prob[-1]] for i in range(len(prob) - 2, -1, -1): prob_meet.append(prob_meet[-1] + prob[i]) prob_meet.reverse() # this[i] GIVEN THAT we've hit at least i test cases, what's the expected value? meet_exp_val = [test_num] outcome_num = 1 total_vals = test_num for tcn in range(test_num - 1, -1, -1): outcome_num += comb_vals[tcn] total_vals += comb_vals[tcn] * tcn meet_exp_val.append(Decimal(total_vals) / outcome_num) meet_exp_val.reverse() # this[i] = same thing as above but given that we've hit STRICTLY UNDER i test cases under_exp_val = [0, 0] outcome_num = 1 total_vals = 0 for tcn in range(1, test_num + 1): outcome_num += comb_vals[tcn] total_vals += comb_vals[tcn] * tcn under_exp_val.append(Decimal(total_vals) / outcome_num) best_val = 0 for strat in range(test_num + 1): p_meet = prob_meet[strat] meet_exp = meet_exp_val[strat] p_under = 1 - p_meet under_exp = under_exp_val[strat] hit_target = p_meet * (p_under ** sub_num - 1) / (p_under - 1) dont = p_under ** sub_num print(meet_exp * hit_target + under_exp * dont) best_val = max( best_val, meet_exp * hit_target + under_exp * dont ) print(best_val + 1) # +1 for the sample # 25 97 should output 17.908380127142752664
I defined a “strategy” as a point where Bessie goes “Good enough for me”.
All the arrays are defined in the code with comments.
for loop at the bottom of the code calculates for each
strat the expected value.
hit_target is the chance that Bessie hits her expectation, and
dont is the chance she doesn’t hit her expectation.
This program fails on all cases except the sample ones. I’ve tried downloading the data, but all of them are too large to solve by hand.