Editorial for COCI '12 Contest 1 #3 Koncert


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 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

There are no comments at the moment.