Description

In a military airbase somewhere in South East Asia, there are 3 distinct types of aircrafts: Air Superiority, SEAD, and Ground Support. Each type of them serves a different role. You, a high-ranking Air Force officer, needs to assign an available aircraft of the specific type to every task in a mission.

 

Rules

Prefix	Task	Type	Type_Base_Cost
FalconPrince	Bogey	Air Superiority	7
EerieProphet	SAM	SEAD	5
FuriousThunder	GolfSierra	Ground Support	4

 

Sort the aircrafts in the input using the following keys: (see Input section for more info)

• Type (First)
• Model index (Second, descending)
• Serial number (Third, ascending)

Then, for each task you receive, find the first aircraft of the same type in the sorted array and print out its ID.

 

Model Index

• Each index corresponds to a capital letter. (see Input section)​
• Input "EerieProphet 01 1" means that it is a version 1 SEAD type aircraft. (ID = EerieProphet01A)

 

Key Priorities

• Type: Air Superiority > SEAD > Ground Support
• Model index: greater > smaller
  • ​E.g., FalconPrince433F > FalconPrince217E
• Serial number: smaller > greater
  • ​E.g., EerieProphet02B > EerieProphet04B

 

Constraints

• You can only use <iostream>, <string>, and <vector>.
• An aircraft can only be assigned to one task.

 

Testcases

• First 3 test cases only have aircrafts with the same model index.
• Testcase #7, #8 includes a new special input. (see below)

 

 

Testcase #7 & #8 (Strongly suggest you come back after solving #1 ~ #6)

Every aircraft has a maintenance cost calculated as follows: aircraft_type_base_cost + model index. You need to sort the aircrafts that have been assigned for tasks according to their maintenance costs in descending order, and print out the IDs of the aircrafts that have maintenance costs >= maintenance_threshold. If two aircrafts have the same maintenance cost, apply the priority in testcase #1 to #6.

 

Reminder

Directly applying O(nlogn) sorting algorithms like merge sort from testcase #1 to #6 may cause TLE. You need to think carefully on how to add a new sorting that specifically solves these two testcases. You don't have to rewrite your whole program.

Hint

• One apporach: what sorting techniques are best for handling very large data consisting of a lot of duplicated values?
• Non-comparison...

 

Gallery (You can skip the part)

EerieProphet: Northrop Grumman EA-6B Prowler  (Source: Broken Arrow)

 

FalconPrince: McDonnell Douglas F-4 Phantom II  (Source: Google Images)

 

FuriousThunder: Republic F-105 Thunderchief  (Source: Google Images)

 

Input

The input consists of two parts: Aircraft and Mission.

Aircraft

• Each input is in the format: [Aircraft Prefix] [Serial Number] [Model Index].
• An aircraft ID contains the type prefix, the serial number , and the model letter.
• Examples
  • ​"FalconPrince 35 3" -> FalconPrince35E
  • "FuriousThunder 76 2" -> FuriousThunder76B
• ​"01" <= serial number <= "40000". Serial numbers of different types and models are counted separately.
• 1 <= Model Index <= 5
  • ​1 = 'A'
  • 2 = 'B'
  • 3 = 'E'
  • 4 = 'F'
  • 5 = 'G'

 

Mission​

• Starts with a "MISSION" input.
• In each line is one of the following tasks:​
  • Bogey
  • SAM
  • GolfSierra
• ​The input ends with an EOF.

 

 

Testcase #7 & #8 (Come back after solving #1 ~ #6)

The last input (right before the EOF) will be a new command:

• "EmergencyMaintenance [maintenance_threshold]"

Example

 

Output

The first line will be "SORTIE". In the followiing lines, print out the IDs of the aircrafts that have been assigned for tasks. The IDs should be grouped by the types of task and printed out in the order: Air Superiority -> SEAD -> Ground Support.

Format

• SORTIE (first line)
• [TASK TYPE][newline]
• [Aircraft ID][space][Aircraft ID][space]...[space][newline]

 

 

Testcase #7 & #8 (Come back after solving #1 ~ #6)

Print out "Under Maintenance" with a newline, then the IDs of the aircrafts that have maintenance costs >= maintenance_threshold, in the same format as the other testcases.

Example

 

Sample Input  Download

Sample Output  Download

Tags

Discuss