#P4736. Airline Seat Assignment
Airline Seat Assignment
Airline Seat Assignment
A low‐budget airline wishes to assign seats to the next n passengers in a sophisticated way. The airplane has \( r \) rows of seats (where \( r \) is an even integer) along with 3 exit rows. The rows are numbered from 1 to \( r+3 \) from front to back. The exit rows are fixed: row 1 (front), row \( \frac{r}{2}+2 \) (middle) and row \( r+3 \) (back), and the other rows are seat rows.
In each seat row the configuration is 3–3–3 (the pattern is ABC.DEF.GHI) where the dots represent aisles. Some seats might already be reserved. When a new ticket is purchased the seat is assigned as follows:
- If there is at least one empty seat in any row that immediately follows an exit row, then only those rows are considered. Otherwise, all seat rows with at least one empty seat are considered.
- From the considered rows, choose the row with the largest number of empty seats. In the event of a tie, choose the row whose minimum distance to any exit row (distance measured as \(|a-b|\)) is smallest. If there is still a tie, choose the row with the smallest row number.
- Within the selected row, determine the empty seat(s) with the highest priority. The seat priorities are (from highest to lowest):
(a) Aisle seats in the middle group (letters \( D \) or \( F \)) — priority 1.
(b) Aisle seats in the first and third groups (letters \( C \) or \( G \)) — priority 2.
(c) Window seats (letters \( A \) or \( I \)) — priority 3.
(d) The middle seat in the middle group (letter \( E \)) — priority 4.
(e) Other middle seats (letters \( B \) or \( H \)) — priority 5. - If there are two or more empty seats with the same highest priority, then consider the overall balance of the airplane. The airplane’s left side consists of seats with letters \( A, B, C, \) and \( D \), and the right side consists of seats with letters \( F, G, H, \) and \( I \). Compute the total number of empty seats across all seat rows on each side. Then, among the candidate seats, select one belonging to the side with more empty seats. If the counts are equal, choose a seat on the left side. If there is still more than one choice, pick the one with the smallest letter lexicographically.
Given the current reservations and the next n passengers purchasing tickets, determine the seat assignments for these passengers.
inputFormat
The input is provided from standard input in the following format:
r n
m
reserved_seat_1
reserved_seat_2
...
reserved_seat_m
Where:
- \( r \) is an even integer representing the number of seat rows (excluding exit rows).
- \( n \) is the number of passengers to assign seats to.
- \( m \) is the number of already reserved seats.
- Each reserved seat is given as a string combining the row number and a seat letter (one of A, B, C, D, E, F, G, H, I). Note that exit rows (rows 1, \( \frac{r}{2}+2 \), and \( r+3 \)) never have seats.
outputFormat
Print exactly ( n ) lines to standard output. The ( i)-th line should contain the seat assigned to the ( i)-th passenger in the format: row number immediately followed by the seat letter (for example, 12F).
sample
4 1
0
2D