Editorial for COCI '12 Contest 1 #3 Koncert
Submitting an official solution before solving the problem yourself is a bannable offence.
Notice that the solution is trivial if the number of tickets is greater than or equal to the number of guys. We can simply use a sequence of GIVE
commands until each guy has a ticket. After that, all guys can enter.
Otherwise, the key observation is: if there are at least two tickets, two people can enter the venue. After that, one person can give their ticket to the other, who can then exit the venue. After this sequence, there is one more person in the venue, while there are still at least two tickets outside.
It follows that we can choose a guy or girl to act as a "courier", i.e. enter the venue with other guys, take their tickets and give them to guys outside. We can repeat this procedure until all guys are in the venue, perhaps save for the courier (if a male one was chosen), who can simply enter with the ticket(s) he has.
Comments