Description

Source: Google

 

EIAD

You are tasked to design the control unit of the cutting-edge, ground-based air defense system EIAD (Extended-range Intercept Air Defense). The system manages a very long target sequence (implemented using linked list) to store the information of incoming bogeys. A bogey, by one of its definitions, is a human aircraft that hasn't been identified as a friendly or enemy yet.

 

IFF

Identification Friendly or Foe (IFF) is a real-world system for distinguishing friendlies from enemies, and vice versa. You are asked to implement a rudimentary (basic) IFF functionality for EIAD.​​​​

• A friendly bogey should be removed from the linked list without being intercepted.
• This is done by calling find_friendly().

 

Implementation & Template

To make EIAD into realization, you must implement the following core features in this air defense system:

• acquire()
  • ​​Insert bogey into the target linked list and update the length of the list.
• find_friendly()
  • ​Given a friendly bogey ID, find whether the bogey is inside the target linked list. (see Input section)
• intercept()
  • At each iteration, traverse the target linked list.
  • Update the distance and update_time of each bogey.
  • If a bogey's distance <= identification_distance, do something. (see Output section)
  • ​Intercept any bogey that is <= engage_distance. (see Output section)
  • If a bogey is <= danger_distance, simply remove it from the list and do nothing.
• reload()
  • ​When EIAD runs out of missiles, it calls reload() and enters cooldown (duration: RT). (see Input section)
  • When reloaded, the number of missiles goes back to M. (see Input section)
  • You can build your own reloading mechanism as long as it works correctly.
• clear_sky()
  • ​Check whether the linked list is empty. If true, output the final message and terminate the program. (see Output section)
• Data Flow​ (Read with Caution)​
  • ​Every bogey must go thorugh the process in the following order: (at each iteration)
    • -> Acquire
    • -> Presumed Hostile (<=1500)
    • -> Intercept (if Presumed Hostile and <=1000)
    • -> Remove the bogey from the linked list
  • A bogey cannot and will not be identified and intercepted more than once.
  • In each iteration, only intercept() or find_friendly() will be called once based on the input. They will not be called within the same iteration.

 

References

• Template BogeyNode:​
  • ​ID
  • Distance
  • Last_update_time
  • Is_identified
  • BogeyNode *next
• Distance parameters: (unit in meter)
  • identification_distance = 1500
  • engage_distance = 1000
  • danger_distance = 250

 

Rules & Notes

• You can only use <iostream> and <string>. Other libraries are not allowed.
• Timestamp is a counter (variable) you need to maintain throughout the entire process.
  • It begins at 0 and starts counting from the first "Bogey" input.
  • Timestamp increments by 1 after each iteration.
• Every bogey travel at the speed of 50 meters per timestamp.
• If EIAD calls reload() at timestamp t, it will go back to intercept hostile bogeys at t + RT.

 

Input

 

The first line consists of:

M RT

From the 2^nd line and onward: (with an EOF at the end)

Bogey ID Dist

Constraints

• M: the number of missiles that EIAD have before reloading, where 4 <= M <= 16.
• RT: the time for EIAD to reload its missiles, where 3 <= RT <= 6.
• ID: the id of a bogey. Each ID is guaranteed to be unique.
• Dist: the initial distance of a bogey, where 500 <= Dist <= 4000
  • ​If Dist = -1, it means that the bogey is friendly. You should look for it in the linked list and generate outputs accordingly.
• N: the total number of incoming bogeys, where 1 <= N <= 7500.
• The first 4 testcases are guaranteed to not have input distance > 1500.

 

Output

 

• {} means the item inside is a variable.
• If a bogey ID is friendly and can be found in the linked list: (input Dist = -1)
  • Tracking {ID}: Bogey Identified As Blue At Zulu Time {timestamp}

 

• If a bogey ID is friendly but is not found in the linked list: (input Dist = -1)
  • Tracking {ID}: Blue On Blue Incident! Feel Sad :( At Zulu Time {timestamp}

 

• If a bogey's distance <= identification_distance:
  • Tracking {ID}: Bogey Presumed To Be Hostile At Zulu Time {timestamp}

 

• When a bogey is intercepted:
  • {ID} Intercepted At Zulu Time {timestamp}

 

Print out a newline character at the end of each output. When there clear_sky() returns true, print out "The Sky is Clear!" with a newline and terminate the program.

 

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Today it's May 4th, so let's celebrate Star Wars Day by building a taxi service for the rebels!

The system needs to have the following commands:

• addRider <rider_id> <rider_val>
  • ​Add a new rider to the system with ids <rider_id> and <rider_val>, which are values computed by AI to represent their classified information.​
• addDriver <driver_id> <driver_val>
  • ​Add a new driver to the system with ids <driver_id> and <driver_val>, which are values computed by AI to represent their classified information.
• match
  • Match a driver with a rider following these rules:​
    • Match the driver with the highest <driver_val> and rider with the highest <rider_val>
    • If there are 2 drivers/riders with the same <driver_val>/<rider_val>, the one who is added earlier to the system has higher priority. 
    • Output (<driver_id>, <rider_id>) and remove both driver and rider from the system.

Note

• If there are only no driver or no rider available for matching, output (-1, -1).
• You need to select the suitable tree structure and representation method for the request. 
• Only <iostream>, <string>, <vector> are allowed for this question.

Input

First line contains an integer N denoting the number of input commands.

Every one of the N lines will be one of the three commands.

 

1<= # of drivers/riders used in process <= 500000

1 <= <rider_id>, <rider_val>, <driver_id>, <driver_val> <= 500000

All <driver_id>/<rider_id> are unique.

 

For testcases 1-5, all <driver_val>/<rider_val> are unique

For testcases 5/7/8, N>=100000, you need to implement an efficient solution for passing them. 

Output

For every match command, output  (<driver_id>, <rider_id>)  with a newline character.

You don't need to output anything for other commands.

Remember to output (-1, -1) if there are no driver/rider available to match.

Sample Input  Download

Sample Output  Download

Tags

Discuss

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.

 

Sample Input  Download

Sample Output  Download

Tags

Discuss