Boeing Seats
Autumn Tournament (2022)
Submission name: boeing.cpp
Problem summary
Seats are sold in row-number order and then letter order. Row 1 has D, E, F; rows 2 through 20 have A through F; row 21 has D, E. One given seat is reserved before sales and cannot be sold. After n tickets have been sold, find the first free seat, or report full.
Input
The sold-ticket count n, then the reserved seat label without spaces.
Output
The first free seat label, or full.
Constraints
0 ≤ n ≤ 118; the reserved label identifies an existing seat.
Worked example
Original statement, example 1.
Input
4 1E
Output
2C
Solution analysis
- Generate the 119 existing seats in their sale order. Skip the reserved seat entirely, leaving 118 saleable seats.
- Scan this order, consuming one sold ticket for each non-reserved seat until n reaches zero. The next non-reserved seat is the answer. If none remains, print full.
- With 1E reserved and four tickets sold, the occupied saleable seats are 1D, 1F, 2A, 2B. The first free seat is therefore 2C.
Why it works
The scan visits precisely the saleable seats in the prescribed order. After consuming n entries, precisely the first n saleable seats have been sold, so the next entry is the first free seat. Exhaustion means every saleable seat is occupied.
Watch out. Skip the reserved seat even when it would otherwise be the next free one. There are 119 seats but only 118 tickets.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: The scan visits precisely the saleable seats in the prescribed order. After consuming n
// entries, precisely the first n saleable seats have been sold, so the next entry is the first free
// seat.
#include<iostream>
#include<string>
using namespace std;
int main(){
int sold;
string reserved;
cin>>sold>>reserved;
for(int row=1;row<=21;++row){
string letters=row==1?"DEF":(row==21?"DE":"ABCDEF");
for(char letter:letters){
string seat=to_string(row)+letter;
if(seat==reserved){
continue;
}
if(sold==0){
cout<<seat<<'\n';
return 0;
}
--sold;
}
}
cout<<"full\n";
}