Concert Tickets
Time limit1sMemory limit128 MB
Given which guys and girls hold tickets, output enter, exit, and ticket transfer actions so every girl leaves the venue while the number of guys with tickets inside is maximized.
- Level
Medium5 of 10
- Topics
- Greedy, Simulation, Implementation
- Solved
- No attempts yet
Problem
M guys and N girls are waiting in front of a concert venue. Some of them already have a ticket, while the others still hope to get one. One performer has just canceled, and all tickets are already sold out.
The girls no longer want to stay in the venue because their favorite performer will not appear. The guys, however, all want to stay. Tickets are not assigned to specific people, so a girl with a ticket may give that ticket to a guy.
Each person initially has either zero or one ticket. Later, one person may carry any number of tickets. A person who has at least one ticket may give one ticket to any other person on the same side of the entrance: either both in front of the entrance or both inside the venue. A person may enter the venue only if they have a ticket, and they keep the ticket after entering. A person inside the venue may exit with or without a ticket, keeping any ticket they have when they exit.
Output one sequence of entering, exiting, and ticket-giving actions such that every girl ends outside the venue and the number of guys inside the venue is as large as possible.
Input
The first line contains two positive integers M and A. M is the number of guys, and A is the number of guys who initially have a ticket. Each guy is identified by a distinct integer from 1 to M.
The second line contains the A identifiers of the guys with tickets, in increasing order.
The third line contains two positive integers N and B. N is the number of girls, and B is the number of girls who initially have a ticket. Each girl is identified by a distinct integer from 1 to N.
The fourth line contains the B identifiers of the girls with tickets, in increasing order.
Constraints:
- 1 ≤ M ≤ 100,000
- 1 ≤ A ≤ M
- 1 ≤ N ≤ 100,000
- 1 ≤ B ≤ N
Output
Output any sequence of actions satisfying the requirements. The sequence must contain at most 1,000,000 actions, and each action must be printed on its own line. X and Y denote identifiers of guys or girls.
Print a guy entering the venue as ENTER GUY X, and a girl entering as ENTER GIRL X.
Print a guy exiting the venue as EXIT GUY X, and a girl exiting as EXIT GIRL X.
Print a ticket transfer as one of GIVE GUY X GUY Y, GIVE GUY X GIRL Y, GIVE GIRL X GUY Y, or GIVE GIRL X GIRL Y, according to the genders of the giver and receiver.