Editorial for COCI '10 Contest 6 #3 Razine


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Notice that there is no point in reducing the number of points for the last level. Now let's take a look at the level right before the last one. If this level is already worth less points than the last one, we don't need to reduce. If this level is worth more points, we reduce to the number of points the last level is worth decreased by one. We can now ignore the last level, and proceed in the same manner until we reach the first.

It's not difficult to see that obtained sequence will be strictly increasing, and also that we will be reducing by the minimal possible number of points. Indeed, we didn't reduce anything that we absolutely didn't have to!


Comments

There are no comments at the moment.