Editorial for COCI '09 Contest 4 #5 Kaboom
Submitting an official solution before solving the problem yourself is a bannable offence.
The best way to approach this task is using dynamic programming. We ask ourselves the following question: How many ways are there to fold the left part of the strip into a spiral with
Now note that there are 3 cases:
- left or right end of the strip is folded into a spiral of length
with the last two segments equal, and the other end is not folded at all. - both ends are folded into two spirals with the last two segments equal, and there is a non-folded segment of length
between them. - the strip is not folded at all.
For 1, we sum on all lengths so the total is
Comments