Description

Important Notice: Those who haven't filled in the google form in the pinned announcement (eLearn) quickly fill it.

---

Silver Wolf being the mischievous hacker she is, hacks into the OJ system and modified the problem from Homework1. Originally the things that can be found were:

 Symbol   -    Full Name

1. D    -    Diamond

2. G    -    Gold

3. B    -    Bomb

4. F    -    Flashlight

5. M   -    Magnet

6. C   -    Lucky Clover

7. P   -    Pig

8. _   -    Empty

But she removed Bomb, Flashlight, Magnet, and the Lucky Clover, while adding Virus, Shovel, Coin, and Strange Button. So the things that can be found now are:

 Symbol   -    Full Name

1. D    -    Diamond

2. G    -    Gold

3. S    -    Shovel

4. V    -    Virus

5. C    -    Coin

6. P    -    Pig

7. X    -    Strange Button

8. _    -    Empty

Object Descriptions

In general, the things mentioned above are divided into 3 types: Collectibles, Items, and Entities.

Collectibles

Diamond - Same usage and rule as homework1, when you dig it you put it in your Backpack.

Gold - Same usage and rule as homework1, when you dig it you put it in your Backpack.

Items

Shovel - It will go to your Item Inventory after being dug. When used, you directly dig the last selected location twice. If there’s no path left then do nothing. Multiple Shovels may exist in the map.

Strange Button - It will go to your Item Inventory after being dug. When used, a wall of collectibles will appear at the end of the map (right most side) with Gold appearing on odd index, and Diamond on even. Multiple Buttons may exist in the map.

Coin - It will not go to your Item Inventory after being dug, you are free to implement how to store it. Cannot be used by the player, will automatically get used as a protective measure against Pig and when used, print out “Ding!” with a new line. There can only be 1 Coin in the map.

Entities

Virus - If you were to dig into a Virus, it’s game over! You directly stop all operations and just print out “Game Over!” with a new line followed by printing the whole map with the rule explained below. There can only be 1 Virus in the map.

Pig - Silver Wolf changes the Pig into a Space Pig! Somehow it is not interested in Diamonds but in Gold instead, if you Dig a Pig then it will steal all of your Gold, or unless you have it’s favorite thing, the Coin then it will be satisfied with only taking your Coin. I guess it likes shiny yellow thingy more than Diamonds. Multiple Pigs can exist in the map.

Game Descriptions

Silver Wolf also modified how the Player can dig, now instead of digging from top to bottom, we dig from left to right. For the Item Inventory, it is reversed, we use the newest item first, leaving the oldest item the last in sequence.

The rest of the Player's moving rules are the same as homework, which is “DIG [idx]” and “USE”.

Inventory is for items. Backpack is for collectibles.

 

This is a normal judge problem.

You are allowed to use STL in this problem. 

Input

Same format with homework.

The first line contains three integers:

1. Integer R representing the number of columns on the map.

2. Integer L representing the number of rows on the map.

3. Integer N, representing the number of actions the Player will do.

Starting from the second line, there are L lines each containing R characters. The R characters in each line are separated by a space between each of them, each character represents an object. Overall, in the initial state of the game, there will be at most R x L items on the map. The empty space in the grid of the stage that doesn't contain any item will be represented by a “_”. You must implement the map by creating an array/vector of queues! You’re not allowed to use a 2D array/vector.

Following the L lines will be N lines, each representing the action the Player will take. Each of these N lines starts with an action string Ai. There will be only 2 available actions: DIG and USE.

DIG will let the user input a number which specifies the position (row) where he wants to dig, if it is an invalid position, do nothing. While USE will directly let the user use the most recent Item the Player gets, if the Item Inventory is empty, then do nothing.

Output

When Player uses a DIG, if they find Virus print “Game Over!” with a new line and then followed by the rule below, if a Pig is found and the Player is protected by Coin, print “Ding!” with a new line. Anything else you don’t have to print anything.

If the player already finished moving N times or they DIG Virus, print your content of Backpack in the sequence of the first item you obtained to the last in the format: “Backpack:“ followed by the rest of the collectibles symbol separated with spaces.

Example: “Backpack: G D D G” (Format is [Space][Item] not [Item][Space]) and print a new line at the end.

Then also print the Inventory with exactly the same way as Backpack.

Example: “Inventory: S X S” (Format is [Space][Item] not [Item][Space]) and print a new line at the end.

After that, print the current state of the map with the format: “Map:”, a new line, then the map with format [Object][Space][Object][Space] (don’t forget the new line at the end). If the map is empty, still print everything inside the map (so basically you will print out a matrix of ‘_’).

Example if there's object in map: 

Map:

_ _ G G D 

_ P _ G D 

_ V _ X C 

S _ G G G 

 <----- there's an empty new line here

 

Example if map is empty:

Map:

_ _ _ _ 

_ _ _ _ 

_ _ _ _ 

 <----- there's an empty new line here

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

 

You are a renowned Pokémon trainer known for collecting battle badges worldwide. Now, you face the final gym challenge to earn your last badge in the ultimate test of skill and strategy – "Badge Quest: The Multiverse Challenge."

The gym leader detests conventional battles and prefers a game with flair, spanning across the multiverse. He challenges you and your partner Mewtwo to this intricate game, where each list represents a different dimension or realm within the multiverse. If you emerge victorious, you'll claim the final badge, proving your mastery over not just one, but multiple dimensions.

Beside you stands Mewtwo, your loyal partner, his keen intellect and formidable power serving as valuable assets in this daunting task. As you both prepare to face the challenge ahead, Mewtwo's unease is palpable. "Do you think we're prepared for this, Trainer?" he inquires, his voice tinged with uncertainty. 

You meet Mewtwo's gaze with a reassuring smile, your confidence unwavering. "Nah, I'd win," you reply, your tone firm and resolute. " He is the challenger here."

With a nod of understanding between you, Mewtwo finds solace in your unwavering belief. With your bond strengthened and determination steeled, you both set forth to navigate the complexities of the multiverse and emerge victorious in this epic battle of skill and strategy.

Summary:

Given n lists representing different dimensions and x commands, determine the final arrangement of Pokémon after executing the operations across the multiverse.

 

Commands:

• Insert int1 int2 int3: Summon a Pokémon into the list at index int1. The Pokémon's ID will be int2, and its level will be int3.
• Remove int1 int2: Remove all Pokémon with the ID int2 from the list at index int1.
• Rotate int1 int2: Rotate int2 times. With each rotation, the last node in the list at index int1 will be moved to the beginning of the same list.
• Reorder int: Rearrange nodes based on their indices. In the list at index int, group all nodes with even indices together, followed by the nodes with odd indices, and return the reordered list.
• Reverse int1 int2 int3: Reverse the order of Pokémon in the list at index int1 within the range of indices [int2, int3].
• MergeListsPreserveOrder int1 int2: Merge the list located at index int2 into the list located at index int1, ensuring that the original order of elements in both lists is maintained. After merging, the elements from both lists will be combined into the list at index int1, with the order of insertion determined by comparing the elements. Elements from the list at index int2 will be inserted into the merged list before elements from the list at index int1 if their Level is smaller, if their level is equal, then the element that has a smaller ID can be inserted first. After merging, the list at index int2 will become empty.

Hint:

Finish simpler functions first, some test cases only require basic functions. Functions are ordered by difficulty.

Guarantee & Notes:

• For the reverse command: The range specified by int2 and int3 will always be within the size of the list at index int1.
• All indices are zero-based.
• Even indices, inclusive of zero, are considered.
• All lists are empty at the beginning.
• All operations would be valid.

Explanations:

Given 3 lists after some operations.

 

Insert 1 1 1

Reverse 1 2 4

Remove 2 1

List at index 2 will become empty

 

Rotate 1 2

 

Reorder 1

Original -> {1, 2, 3, 2, 1},  Reordered -> {1, 3, 1, 2, 2}

 

MergeListsPreserveOrder 0 1

We will use different lists to demonstrate this operation for better understanding.

Before

After

Input

1. Frist line will consists of an integer n which indicates the total number of lists. Where n is (1 <= n <= 10)

2. Second line will consists of an integer x which indicates the total number of commands. Where x is (1 <= x <= 10000)

3. The following x lines will contain one of the following commands:

Insert int1 int2 int3 (0 <= int1 < n) (1 <= int2, int3 <= 100)

Reverse int1 int2 int3 (0 <= int1 < n) (0 <=int2, int3 < size of list at index int1)

Remove int1 int2 (0 <= int1 < n) (1 <= int2 <= 100)

Rotate int1 int2 (0 <= int1 < n) (1 <= int2 <= 10000 )

Reorder int1 (0 <= int1 < n)

MergeListsPreserveOrder int1 int2 (0 <= int1, int2 < n) (int1 != int2)

Output

Print out the List index and the pokemon ID and Level in this list.

If list is empty, print Empty.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

In this Quiz you need to do several steps of Binary Tree manipulation to get the desired output. Refer to the following instructions regarding the functions that you need to implement.

Insert [index] [parent_value] [value]

Insert the node to the tree at the specified [index] with the given [value] under the selected node that has value [parent_value]. We insert starting from the left child of parent, to the right child, if the selected parent already has 2 children then do nothing. If the container at the specified [index] is empty, then ignore [parent_value] and assign the new node as the root of that tree else if the container is not empty and there's no node that has [parent_value] in the tree then do nothing.

Delete [index] [value]

Delete the node of the tree at the specified [index] that contains the given value. Any children of that deleted node will be cut off too from that tree. If the node with the given [value] doesn’t exist on that tree then do nothing.

Print [index] [mode]

Print the tree at the specified [index] depending on the [mode]: pre for preorder, in for inorder, and post for postorder. The format is [Node Value][Space] and at the end print a new line. If it’s empty just print a new line.

Max [index]

Print the maximum value in that tree then a new line. If the tree at [index] is empty, do nothing.

Merge [destination] [from] [value]

Merge 2 different trees, make a new parent node with the given [value], then the left child being the tree at index [destination] and right child being the tree at index [from]. The new parent node now stays at index [destination] while the container at index [from] is now empty.

Disjoint [index] [value]

Find the node with the given [value] at the specified [index] tree, and then make it as a standalone tree. Move this subtree to the first empty index in your chosen data structure (container), if all of them already have a tree stored, then increase the storage size by 1 (meaning now the size of the container may go over the initial size and may goes beyond 10 during the operations) and move it there. If there’s no node that has the given [value] then do nothing. If the node that has the given [value] is the root of that tree, just move the whole tree based on the rule mentioned before. (Hint: First, search the node then cut it off before looking for index that is not full)

Visualization

4 20

Insert 0 10 0 -> Insert 1 11 1 -> Insert 2 12 2 -> Insert 3 13 3 (All of them is root so ignore parent)

Insert 0 0 4 -> Insert 0 0 5 -> Insert 0 0 6 (Node 0 is full so it’s not inserted) -> Insert 0 4 6

Print 0 pre -> Print 0 in -> Print 0 post -> Max 0

0 4 6 5  -> 6 4 0 5  -> 6 4 5 0  -> 6

Merge 0 1 30

Print 0 pre -> Print 0 in -> Print 0 post

30 0 4 6 5 1  -> 6 4 0 5 30 1  -> 6 4 5 0 1 30 

Disjoint 0 4 (The subtree is moved to Tree 1 because it’s empty there)

Delete 0 0

Disjoint 1 6 (We extend the container because Tree 0 ~ 3 are already full)

Delete 0 0 (Do nothing because Node 0 doesn’t exist)

Final Output:

Input

In the first line you will be given the initial size of the container [n] and the number of operations we will do [ops].

Followed by [ops] number of lines which will be a series of operations that has been mentioned above.

Limit:

1 <= n <= 10 

1 <= ops <= 100

0 <= index, destination, from < n

0 <= value (guaranteed unique), parent_value <= 100

parent will always exist

Output

When we do the operation Print, we output the tree based on the traversal mode specified at the given index. Please note that the format of printing is [Node_val][Space] and then a new line at the end.

When we do the operation Max, we output the highest value in that tree. Please note that the format is just [Max_val] and new line, there's no space after the maximum value.

When the program ends, print all the trees inside the container using inorder traversal with the following format (don’t forget to print a new line after all the nodes are printed):

Tree 0

A B C D E 

Tree 1

F G H 

…

Tree n-1

X Y Z 

 

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A bus company is planning to optimize its city routes, and they've enlisted Panda's help to ensure the city is well-connected. The city is represented as a weighted directed graph, where each bus stop is a node, and the routes between them are edges with different travel times. The company wants to ensure that the main terminal(s), Terminal A and/or Terminal B, have optimal routes to the downtown hub, City Center. As the route planner, your job is to find the shortest subgraph that can guarantee efficient routes from the specified terminal(s) to the City Center.

Example Question:

Given the Input:

n = 3

m = 3

edges -> 0, 1, 2 | 0, 2, 3 | 1, 2, 3  

t = 2

A = 0, B = 1, City Center = 2.

Output: 5

Given the Input:

n = 2

m = 1

edges -> 0, 1, 2

t = 1

A = 1, City Center = 0

Output: -1

 

Given the Input:

n = 3

m = 2

edges -> 1, 0, 2 | 2, 0, 5

t = 2

A = 1, B = 2, City Center = 0

Output: 7

Hint

Start by handling the condition where there's only one terminal.

Input

You are given an integer n, representing the number of bus stops in the city. The stops are numbered from 0 to n - 1. 

You are given an integer m, representing how many edges will be provided, followed by m lines where each line consists of three numbers ‘fromi toi wi’ representing a bus route from stop fromi to stop toi with a travel time of wi. 

You are also given an additional integer t, which specifies how many terminals should have routes to the City Center (1 <= t <= 2):

 • If t = 1, only Terminal A (A) will be considered, and the input will only contain A and dest. 

• If t = 2, both Terminal A (A) and Terminal B (B) must have optimal routes to the City Center city (dest).  Additionally, you are given up to three distinct integers A, B, and dest, representing the stops for Terminal A (A), Terminal B (B), and City Center (dest), respectively. 

Constraints:

2 <= n <= 100000

0 <= m <= 100000

0 <= from, to, A, B,  City Center <= n – 1

from != to / A != B != City Center

1 <= w <= 100000

Output

Your task is to determine the minimum travel time of a subgraph that allows passengers to travel from the specified terminal(s) to the City Center (dest): 

1. If t = 1, find the shortest subgraph from Terminal A (A) to the City Center. 

2. If t = 2, find the shortest subgraph that allows passengers to travel from both Terminal A (A) and Terminal B (B) to the City Center (dest).  If it's impossible to reach the City Center from the specified terminal(s), return -1.  

Remember end of line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

In the ancient kingdom of Numeria, a land ruled by the arcane order of Mathemagicians, you are challenged to a game of "Consecutive Swap Chess". This game is played on a linear board numbered from 1 to n, with each square uniquely occupied by enchanted stones numbered from 1 to n. The initial arrangement of the stones is given as an array: [p[1],p[2],...,p[n]].

The Mathemagicians allow you to make moves under a magical constraint: You may only swap two stones if their numerical difference is exactly one, suggesting a mystical bond between consecutive numbers, which means pick two indices x and y such that |p[x] − p[y]| = 1.Your task is to appease the Mathemagicians by transforming the board into a state of ascending tranquility, where each stone p[i] aligns perfectly with its board position i (i.e. p[i] = i for all i ∈ {1,2,…,n})

Hint:

1. Understanding Inversions:
   Delve into the concept of inversion pairs in an array, where an inversion occurs when a larger number precedes a smaller one. For instance, in the array [3,1,2], there are two inversions: 3 precedes 1 and 3 precedes 2. Understanding and identifying these inversions is pivotal in developing a solution for sorting the array.
2. Test Case 1~3 for O(n²) or O(n³) Complexity:
   Consider designing a test case that allows for a solution with a time complexity of O(n³). This might involve checking each possible pair multiple times, ideal for a smaller dataset where such complexity is manageable.
3. Test Case 4~5 for O(nlogn) Complexity:
   Prepare a test case that is efficiently solvable using O(nlogn)\ algorithms. This often involves techniques like divide and conquer, which are suitable for sorting problems and can handle larger data sets effectively.

Input

The input consists of two lines: The first line contains a single integer n, representing the size of the array. The second line contains n space-separated integers [p[1],p[2],...,p[n]], which represent the elements of the array.

• 1 < n ≦ 200,000
• 1 ≦ p[i] ≦ n
• Each p[i] is distinct and appears exactly once in the array.

Output

Output only one number that denotes the minimum number of operations required to sort the given array.

Please print ''\n'' after your output number

Sample Input  Download

Sample Output  Download

Tags

Discuss