← All solutions

Shortest judge solution: 643 bytes. Shortest team solution (during contest): 741 bytes.

The solution to this problem will simulate Danny’s optimal behavior for as long as possible, to find the answer. The first issue to deal with is the “forever” answer — for how long do we need to simulate before we can safely claim that Danny will be able to eat sweets forever.

Let A denote the sum of all a_i. Notice that if at whatever point Danny has n sweets, where n is positive and divisible by A, then the numbers n f_i − 1 and n f_i + 1 are integers. Thus, there is only one possible choice of the number of sweets of any given type, for all the types, and so s_i = n f_i. If we extend the sequence cyclically (that is, the n + 1st sweet is equal to the 1st, the n + 2nd is equal to the second, and so on), then it will always be balanced — because in the inequalities, all three expressions increase by n f_i.

So, we need to simulate just to the nearest multiple of A. Since A is at most 10⁵, this means we need to be able to simulate a single step (single choice of a sweet) in logarithmic time.

This, in its heart, is a scheduling problem. For any sweet type i, there is some minimum total number of sweets we need to have to be able to buy the kth sweet of that type (let’s call that number L(i, k)), and some maximum total number of sweets, where if we did not buy the kth sweet of type i and we already have this number of sweets, then our diet is already unbalanced (let’s call that number U(i, k)). The solution (as usually with scheduling problems) is to always take the element which has the earliest deadline — so, in this case, the sweet with the lowest U(i, k) value. The proof is a relatively standard exchange argument, which we leave to the reader.

Implementation-wise, we can hold two priority queues — the queue of sweets we can’t yet buy, ordered by L(i, k), and the queue of sweets we can buy, ordered by U(i, k). Notice that we know up front which sweets we will need to buy to get up to A, so we can begin by inserting them all into the appropriate queues. At each day, begin by moving sweets that we can now buy from the first queue to the second, and then pick the first sweet from the second queue and buy it. If it turns out that is was already expired when we buy it, the previous day was the last we could have had a balanced diet, otherwise we proceed.

One simplification that we can apply to this is that the first queue is in fact not required: if we assume all the sweets are available immediately, the solution may start constructing unbalanced sequences, but it will not be able to extend the sequence to a larger number of days, so the answer remains the same. The proof is rather standard, but a bit technical, so we will skip it.