Let's sequence S(n) = {s[1], s[2], ..., s[n]} is optimal sequence for the first n steps. L[i] is max number when we can get one space using S(n) for any number in range [1..L[i]]: firstly, we apply s[n], then s[n-1] and etc.
Now let's get next s[n+1]. Suppose we found s[n+1] and want get L[n+1]. Always L[n+1] + 1 = q*s[n+1] + r, 0<=r<s[n+1]. L[n+1] is max number => for L[n+1] + 1 we need at least n+2 steps => q + r >= L[n] + 1. But L[n+1] + 1 is min number when using S(n+1) we can't get one space => r->max, q->min =>
r = s[n+1] - 1, q = L[n] + 1 - r =>
L[n+1] + 1 = q * s[n+1] + r =>
L[n+1] = (L[n] - s[n+1] + 2) * s[n+1] + s[n+1] - 2 -> max (where arg is s[n+1])
=> s[n+1] = (L[n] + 1) / 2
But using symmetry we can give s[n+1] = floor(L[n] / 2) + 1 (we choice bigger number because s[2] > 1).
=> L[n+1] = q * s[n+1] + r - 1, q = L[n] + 1 - r, r = s[n+1] - 1.



Edited by author 26.02.2022 01:27

Edited by author 26.02.2022 01:27