Editorial for COCI '09 Contest 7 #6 Restoran
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.
Submitting an official solution before solving the problem yourself is a bannable offence.
Degree of roads of any given city is the number of roads with endpoints in that city. First we create an additional city , and connect it to all cities with odd degree of roads. It can be shown that this leaves no cities with odd degree (including
). This means that the graph is Eulerian, or if not connected, that each of its components is Eulerian. We now find Eulerian cycles in all components and allocate building rights on them alternating between
and
.
For each component with at least one odd degreed city, this is a viable solution. For components with no odd degrees, there are two cases:
- One degree larger than or equal to
. Starting from such degree forms a correct solution.
- All degrees equal to
. The component is a cycle. If it contains an even number of cities, it is possible. Otherwise it is impossible to solve this graph.
Comments