A shepherd in the hills of Kesh has a wheel of cheese cut into N slices, and it must last the T days t = 0, 1, \ldots, T-1 until the pass opens. On each day she eats a whole number of slices c_t, anything from 0 to what is left; nothing spoils, and nothing new arrives. Eating c slices on one day gives her \sqrt{c} of enjoyment, and she discounts the future with the factor \beta (beta, 0 < \beta \le 1), so a plan is worth
Slices left after day T-1 are worth nothing to her.
Write cheese_plan(N, T, beta) that returns a tuple (value, bites): the largest possible worth of a plan, and a best plan as a list of T bites. If several plans are worth the best amount (within 1e-9), return the one with the smallest first bite; among those, the smallest second bite; and so on.
Examples
Input: N = 10, T = 4, beta = 0.8
Output: (4.80273733, [4, 3, 2, 1])
Explanation: sqrt(4) + 0.8 * sqrt(3) + 0.64 * sqrt(2) + 0.512 * sqrt(1) = 4.8027.
She eats more early, because later enjoyment counts for less.
Input: N = 5, T = 2, beta = 1
Output: (3.14626437, [2, 3])
Explanation: [2, 3] and [3, 2] are both worth sqrt(2) + sqrt(3); the smaller first bite wins.
Input: N = 0, T = 3, beta = 0.9
Output: (0.0, [0, 0, 0])
Constraints
- the value is compared with a tolerance of
1e-6; the bites exactly
Goals
- Write the value of each amount of cheese left on each day as a recursion from the last day backwards
- Record the best bite for every state, then follow those choices forwards from the start
- Break ties between equally good bites by a stated rule