Description

Prowler is the newest file management system in the market, using the following operations to prowl through folders in computers.

• "..": Go to the parent directory of the current directory, no need to move if in '/home' directory
• "./" : Stay in the current directory
• "<folder_name>/": Move to <folder_name>, if <folder_name> doesn't exist in the current directory, create a new folder called <folder_name> in the current directory.
• "pwd": Output the path from 'home' directory to current directory.

Your first job in Prowler is to recreate this system using C++ and one of the data structures you learned last week.

Note: You always start at /home directory

 

 

Input

Input consist of N lines of commands that only include the commands listed above.

<folder_name> will always be a string that only contains upper/lower case letters, underscore('_') and numbers

The last command will always be 'pwd'.

The input ends by reaching end of file(EOF)

N<=100000

Hint: Use while(read command line here) to read the inputs until EOF.

Output

Output the path from '/home' folder to current directory only when processing 'pwd' command.

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

Every output line needs to end with '\n'.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

After the success of Spider-Man's queue service, Spider-Man decided to build a taxi service suited for the citizens of New York City.

Input

First line is an integer N indicating the number of commands.

Following N lines are one of the five commands mentioned above.

All <Driver_id> are unique integers.

All <Rider_id> are unique integers.

1<=N<=100000

1 <= <Driver_id>/<Rider_id> <= 100000

First testcase is similar to sample I/O.

3 of the testcases will not use addGoldenDriver and addGoldenRider command

Output

Everytime when dispatch command is called, output the pair (<Rider_id>, <Driver_id>) and '\n'.

If no availabe driver/rider, return (-1, -1)

No need to output anything for other commands.

Sample Input  Download

Sample Output  Download

Tags

Discuss

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

Tim and Ray are planning a trip to find their friend Sam in Pingtung. To reach their destination as cheaply as possible, they want to minimize the total cost of traveling. On the way, they may stop at a specific location to enjoy the scenery before heading to their final destination. Fortunately, Prof. C has provided them with a limited number of Uber vouchers that allow them to skip the traveling cost of certain roads entirely.

Problem Description

You are given a map consisting of N cities and M undirected roads. Each road has a specific traveling cost (weight).

Key Rules:

• Vouchers (K): You have exactly K Uber vouchers.

• Using a Voucher: One voucher can be used to traverse any one road. When a voucher is used, the cost for that specific road is treated as 0.

• Standard Travel: If you do not use a voucher, you must pay the full cost of the road.

• Goal: Find the minimum total cost required to travel from the Starting City to Destination City 1, and then continue from Destination City 1 to Destination City 2.

Constraints

• 1 ≤ N ≤ 100

• 1 ≤ M ≤ 150

• 0 ≤ K ≤ 3

• 1 ≤  costi ≤  100

• Cities are represented by integers (from 0 to N-1).

NOTE:

• You may use any headers from the C++ Standard Library

Testcases

For this practice I only provide 1 testcase for every category (Total 4 testcases) 

Input

The first line contains three integers:

           N M K

• N: number of cities 

• M: number of undirected roads 

• K: number of vouchers

The next M lines each contain:

           Cityu Cityv costi

• This represents an undirected road between Cityu and Cityv with cost costi.

• Cityu and Cityv  must be different.

• Both cities are guaranteed to appear in the city list.

The last line contains three integers:

           StartCity EndCity1 EndCity2

• Tim and Ray must visit EndCity1 first, then move to EndCity2.

• StartCity is different from EndCity1.

• EndCity1 can be the same as EndCity2 (in which case, the journey ends at EndCity1).

Output

• Print a single integer: the minimum total cost to complete the journey StartCity → EndCity1 → EndCity2.

• If the journey is impossible, print -1.

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

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