Description

SAVE THE BUNNY

Daisy The Bunny and an UAC scientist are held in Phobos Lab by demons from hell in one of the moon bases of UAC. With the help of the DOOM Guy ( ) you will save the scientist and the little bunny. For this, you need to give him the proper route to kill the demons in the most efficient manner and defeat the mastermind programmer behind all of this, i.e. J. Omero, in the final location, i.e. chambers of mastermind. In order to successfully achieve victory over your enemies, our guy needs to have the maximum amount of ammunition (ammo) he can have in the final location.

In the castle, there are several rooms connected by corridors and the corridors are guarded by
Omero’s minions. It would take some of your ammo in order to pass safely through them, although will find some leftover ammo to replenish his weapon. Note also that, each time you pass a corridor, monsters will revive in the next time step. In this quest, first, needs to reach the room containing the skull key that unlocks the door of location which our scientist is kept in. After getting this key, he needs to save scientist that is located in some other room since she has the other skull key that opens the final location.

However, other rooms are problematic too. There is a pattern for the other unlocked doors. Specifically, in each time step some rooms becomes locked some rooms becomes unlocked and it is forbidden for to stay in the same room in sucessive time steps, i.e. he needs to move another room at every time step. For example, let’s say, there are 3 rooms which only the first one is connected to other rooms and there are two periods. In 𝑡𝑡 = 1, only 𝑟𝑟𝑟𝑟𝑟𝑟𝑚𝑚2 is locked, in 𝑡𝑡 = 2 only 𝑟𝑟𝑟𝑟𝑟𝑟𝑚𝑚3 is locked, alternating in each time step. Therefore, starting in 𝑟𝑟𝑟𝑟𝑟𝑟𝑚𝑚1, in 𝑡𝑡 = 2 he needs to move to 𝑟𝑟𝑟𝑟𝑟𝑟𝑚𝑚2 (since our guy shoud not stay in 𝑟𝑟𝑟𝑟𝑟𝑟𝑚𝑚1 and 𝑟𝑟𝑟𝑟𝑟𝑟𝑚𝑚3 is locked in the next time step). Repeating this pattern over succeeding time steps, in 𝑡𝑡 = 3 𝑟𝑟𝑟𝑟𝑟𝑟𝑚𝑚2 is unlocked again whereas 𝑟𝑟𝑟𝑟𝑟𝑟𝑚𝑚3 becomes locked etc. . Here is some remarks:

• cannot stay in a room no longer than one time-step.
• can revisit a room but note that monsters revive each time you pass so you will lose ammunition.
• If encounters a room which has ammunition, you can increase your ammo by the amount stored in the room. However, if herevisits the room, there won’t be ammo any longer.
• There will be two periods in this quest. You will be given the list of locked rooms for these two periods separately; first period represents the odd numbered time-steps, and the second period represents the even numbered time-steps.
• In 𝑡𝑡 = 1, is in room numbered by 1.
• If a room is locked in the next time step, cannot go to that room in that time zone.
• Scientist’s room and the chamber will be closed until opens them with the appropriate keys.
Acquiring keys and opening locked doors with them is an automatic process.
• Journey will end at the chamber.

Here is an example scenario illustrating the sample input. Vertex numbers are room numbers and edge (corridor) numbers are the amounts of ammo that you should use to pass through that corridor.

Input Specifications:

• You should read the inputs from “𝑡𝑡ℎ𝑒𝑒3. 𝑖𝑖𝑖𝑖𝑖𝑖”
• The first line of the input will include one integer, showing the quantity of ammo you have.
• The next line will give one integer representing the total number of rooms, the value of 𝑖𝑖 (3 ≤ 𝑖𝑖 ≤ 10000).
• The next line will have the room number of the chamber (where poor bunny is held).
• The next line will include the room number that the key of scientist’s room is stored.
• The next line will include the room number of scientist’s room.
• Next line will include an integer representing how many rooms are locked in the odd periods followed by the list of rooms locked in odd periods.
• Next line will include an integer representing how many rooms are locked in even periods followed by the list of rooms locked in even periods.
• The next line will give the number of corridors, let us say 𝑚𝑚.
• The next 𝑚𝑚 lines will consist of three integers, the first two are the room numbers connected by the corridor and the third is the ammo amount you should use in order to pass through the corridor.
• Next line will consist of an integer showing the total number of rooms containing ammo, let us say 𝑘𝑘 (0 ≤ 𝑘𝑘 ≤ 10000).
• Each of the next 𝑘𝑘 lines have two integers, first for the room number, second for the amount of ammo you can get from that room.

Sample Input: (𝑡𝑡ℎ𝑒𝑒3. 𝑖𝑖𝑖𝑖𝑖𝑖)
100
7
6
3
4
2 2 7
1 2
10
1 2 3
2 3 1
1 3 5
3 6 7
3 4 1
3 5 2
5 6 5
4 5 3
4 7 2
5 7 2
1
7 3

Output Specifications:

• Output file should have the name “𝑡𝑡ℎ𝑒𝑒3. 𝑟𝑟𝑜𝑜𝑡𝑡”
• In the first line, you should print the number of ammo you have left.
• In the second line, you should give the number of rooms you visited.
• In the third line, you should output the rooms in the order you traversed.

Sample output: (𝑡𝑡ℎ𝑒𝑒3. 𝑟𝑟𝑜𝑜𝑡𝑡)
88
6
1 3 4 7 5 6

REPORT

In this THE, you are going to prepare a report with at-most 2 pages containing the following sections. These sections are must.

1. Proposed Algorithm & Pseudocode
2. Complexity Analysis

In the first section you need to give detailed explanation of your data structures, your approach for solving the problem and details of your algorithm overall. For the second section you need to compute your algorithm’s complexity.

REGULATIONS

• All the work should be done individually. Your THEs will be checked for cheating.
• Submit a single compressed file 𝑡𝑡ℎ𝑒𝑒3. 𝑟𝑟𝑟𝑟𝑟𝑟, 𝑡𝑡ℎ𝑒𝑒3. 𝑡𝑡𝑟𝑟𝑟𝑟 or 𝑡𝑡ℎ𝑒𝑒3. 𝑡𝑡𝑟𝑟𝑟𝑟. 𝑔𝑔𝑔𝑔 via COW system including your code (𝑡𝑡ℎ𝑒𝑒3. 𝑐𝑐𝑖𝑖𝑖𝑖) and report (in pdf format).
• Since black box evaluation method is going to be used, be careful about input/output specifications. You should use space as a delimiter and do not print any unnecessary characters, white spaces etc.

• SAVE THE POOR BUNNY !!!

Weaponizing demons for a brighter tomorrow
– UAC –