Description
You are tasked with organizing military troop transportation via helicopters. To fulfill your responsibility, you have to report all of the helicopters that are assigned for transporting troops.
There are 3 types of helicopters available for dispatch: C (Heavy), B (Medium), and K (Light). Each type is capable of carrying a different amount of personnel.
- C -> 32
- B -> 11
- K -> 4
And for each type of helicopter, you need to maintain an individual linked list. That is, 3 linked lists in total. The lists are initialized as follows:
C -> NULL
B -> NULL
K -> NULL
Requirements & Notes
Your duty is to find the minimum number of helicopters that can accommodate the group of personnel in the input while keeping the vacancy on the helicopters as small as possible, and insert the IDs of the helicopters into the corresponding linked list C, B, or K.
You also need to pay attention to when to remove a specific helicopter from its list due to the need for repairs, and find a new one to replace it.
- You are only allowed to use <iostream> and <string>. Other than these are prohibited.
- Each type of helicopter has its own ID prefix:
- C: MC
- B: MB
- K: MK
- Each ID is followed by a 3-digit string.
- The string starts at "001".
- IDs of different type of helicopters increment separately.
- Priority: less helicopters > less vacant seats
- If the number of personnel falls between two types of helicopters, the one with greater capacity is preferred.
- E.g., (initial or remaining) personnel = 8, and 4 < 8 < 11. We will go for type B rather than type K.
- For each group (input) of personnel, you don't need to find unoccupied seats in the previously assigned helicopters. Instead, create new ones.
Example
Suppose the lists are empty and an input of 35 personnel comes in. In order to carry all of them, you will need 1 C + 1 K = 36 instead of 1 C + 1 B = 43 (more wasted seats). After that, your lists become:
C -> MC001 -> NULL
B -> NULL
K -> MK001 -> NULL
Another input comes in: (personnel = 18). Since we only need one type C helicopter to transport 18 troops, so we choose 1 C = 32 instead of 1 B + 2 K = 19.
C -> MC001 -> MC002 -> NULL
B -> NULL
K -> MK001 -> NULL
And suddenly, "MC001" needs to be under maintenance:
C -> MC002 -> MC003 -> NULL (remove MC001 from the list, then find the next available ID and insert it into the list)
B -> NULL
K -> MK001 -> NULL
Gallery References (you can skip this part)
C (MH-47G Chinook)
Source: Google Images
B (MH-60M Blackhawk)
Source: Google Images
K (MH-6 Little Bird, nicknamed Killer Egg)
Source: TWZ, photographed by Jamie Hunter
Input
The input consists of two kinds of commands:
- Transport PersonnelNum
- PersonnelNum is the number of troop personnel you need to take care of.
- Maintenance ID
- ID is the ID of a helicopter.
- Look up the given ID in the corresponding linked list (which type):
- If it's in the list, assign a new helicopter and add it to that list, then remove the old one from the list.
- If not, do nothing.
- The new helicopter is always added to the end of the list.
- If the ID is not found, do nothing.
- The input ends with an EOF.
Constraints
- It is guaranteed that the total number of personnel will not make the ID of a helicopter of any type exceed 999.
Output
Print out all the helicopter IDs stored in your linked lists in the order C -> B -> K. Also, the IDs should be grouped by their types.
Suppose we have the following lists in the end:
C -> MC002 -> MC003 -> NULL
B -> NULL
K -> MK001 -> NULL
The output will be:
IN ACTION
HEAVY
MC002 -> MC003 -> END
MEDIUM
END
LIGHT
MK001 -> END
Remember to print out a newline character at the end.