Editorial for COCI '09 Contest 6 #2 Natjecanje


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.

This task can be solved using a simple greedy algorithm. First we take care of teams that have lost their kayaks and brought reserves. They are the same as teams that have not lost their kayaks and did not bring reserves, so they can be counted as such. Now, starting from the first team, we work our way up. For each kayakless team, we check their lower-numbered neighbor first, if they can borrow that kayak, then they do it. If not, they check their upper-numbered neighbor. If they have a spare kayak, they borrow that one. If not, they are kayakless and increment the solution by one.


Comments

There are no comments at the moment.