Here's another approach to the problem C of Education round 95. This is a greedy one.
From the beginning, we keep on looking for continuous segments of $$$1$$$'s. We list their lengths as $$$x_1, x_2, \cdots , x_k$$$.
Let the first segment begin in the first position. The optimal strategy, then, will be that my friend kills one boss, and I kill two. If, however, only one is left for me at the end of the segment, I'll kill only that one leaving my friend to deal with the easy boss (if any) following. The number of skip points used in this case is $$$\left\lceil\dfrac{x_1}{3}\right\rceil$$$. We claim that we can't bring it down further. This is true, as my friend is making a minimal number of moves.
For any segments that do not begin with the first position, we have the optimal strategy as follows. Notice that we always have a sequence of moves such that I can open the segment. If unsure, try proving it.
Hope you liked it.
