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 segments with the smallest non-folded piece having length ? And then the same question for the right part. If we know how to answer that, we use the information to answer this: How many ways are there to fold the left (or right) part of the strip into a spiral with the last two non-folded pieces length ? Summing on gives us the number of ways to fold the strip into a spiral of length with at least two equal pieces having the last two pieces of length at least one. We can now extend this even more to: How many ways are there to fold a spiral of length with the last two non-folded pieces equal, that doesn't explode (i.e. the smallest segment is at least or )? Note this number as and .
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 . For 2, we sum on the length of so the total is . For 3, there is only one way to to that. Sum of both these sums plus one is the solution.
Comments