Description

TA Louis is helping out at his cousin’s wedding, his job is to help the guests to find their seat, it is not an easy job because there are hundreds of people attending, and Louis need to keep track of how many guests have arrived and check how much money is in the red envelope, so please help Louis to build a system to record the guest's name.

Because the venue's parking lot is very crowded, Louis wants the first guest to arrive to choose the innermost parking slot and the last guest to select the outermost parking slot so that he can plan a route for guests to leave will smoothly. Help Louis to come up with the plan.

After the preparation is completed, Louis can finally enjoy his meal. But now he has a new job, which is to “block alcohol” for the groom and bride:

(Figure 1: TA Louis wearing a belt saying: Captain of Alcohol)

TA Louis wants you to record the order of toasting, because he will get a hangover afterward, and he wants to recall everything when he wakes up, please help him.
(In Chinese tradition, the groom and bride should toast table by table to thank every guest for coming to the wedding)

Based on the description above, there are 2 things you need to record:

1. The leaving order of the guests (route planning).
2. Toasting order of each table.

Input

There will be several lines of input, every 2 lines represent an event of the wedding.
1. If the input is for route planning, then the first line will be a single character R.  The second line will be name and arrival time of the guest, separated by one space character. The arrival time is recorded as the number of minutes passed.
2. If the input is for toasting order, the first line will be a single character T.  The second line will be the table number and the glasses of alcohol Louis drink, separated by one space character.

Output

1. The leaving order (planned route).  The outermost guest should leave first, in this format:
    1. The name of the guest, each separated by a space character, and an \n at the end.
    2. The time delta between last arrival and first arrival, in minutes, followed by an \n.
2. The toasting order: 
    1. The number of tables, each separated by a space character, and an \n at the end.
    2. The total amount of glasses Louis has drunk, followed by an \n.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Zuma used to be a popular game in the early 2000s. In the game, a track of colorful beads rolls slowly towards a “hole”. The player has to shoot bead into the track, to attempt to form a group of 3 or more continuous beads with the same color. Once formed, the group will be eliminated, effectively slowing down the advancement of the beads.

In this problem, we will have initially N beads on the track and the colors of beads are red, green and blue. You need to shoot a bead with a given color C after the mth bead (count from the first bead on the track and the index starts from one). The bead will connect three or more beads of the same color on the track (form a string with ≥ 3 beads, called STRING), and do one of the following action depending on the beads’ color:

• R - eliminate
  • happen when the color of STRING is Red
  • action: eliminate STRING
• G - double
  • happen when the color of STRING is Green
  • action: double the count of STRING and move to the end of the beads on the track
• B - Reverse
  • happen when the color of STRING is Blue
  • action: move STRING to the front of beads on the track and reverse the order of the beads on the track

After the action, the remaining beads on the track will connect together. If there are three or more beads of the same color connected together due to the action, they will form STRINGS again and do the action depending on the beads’ color. After the beads on the track become static, that is, no more chain reactions will happen, the program is ended. Please provide the final order of the beads on the track (starting with the first bead on the track) and the remaining number of beads.

Input

• The first line (separated by a space), there is a newline at the end.:
  • N: number of the initial beads on the track; 1≤N≤100
  • m: the index of the bead that the shot bead should put after; 1≤m≤100
  • C: the color of the shot bead; C∈{R, G, B}
• After the first line: a series of R, G, B, representing the color of the beads, separated by \n. There is a newline at the end.

Output

• The first line: the final order of the beads on the track
  • Starting with the first bead on the track
  • Consisting of a series of R, G, B, separated by a space. (No space at the end)
  • There is a newline at the end.
• The second line: the remaining number of beads
  • There is a newline at the end.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Background Story

You are a fan of yu-gi-oh but you don’t have yu-gi-oh card.
Therefore, you can only utilize poker cards to simulate simple yu-gi-oh.

Simple Rule Explanation

• Every turn, you will draw a card from a deck of cards then put it on table.

• You can only put two cards on table(left and right side).

• each card has its pattern:

  • Clubs♣️:

    • directly put it on table from left to right(if there is a card on left side then put it to right).
    • It contains 1 point.

  • Diamonds♦️:

    • it should cover on a card.
    • if the covered card is on left side then the covered card will be the left child node of this card, vice versa.
    • if both of the cards on table contain same points, then Diamonds will cover on the left side first.
    • Diamonds♦️ will cover the lowest point card first.
    • It contains 3 points

  • Heart♥️:

    • it should cover on two cards(left side and right side of table).
    • left side card will be its left child node, and right side card will be its right child node.
    • whenever putting this card, we sum the points from its left child nodes and right child nodes.
    • the points sum from its left child and all left child’s child become positive(+), and the points sum from its right child and all right child’s child become negative(-).

  • Spade♠️: whenever you draw this card the game is over.

• In the end, you need to sum the values from all Heart♥️.

  • Some extra hints:
    • If the card you draw cannot be put because of missing conditions. For example: you draw a Diamonds♦️ but there is no card on left side and right side, you will just ignore the card.

Simple Demonstration

• The turns You decides will be like:

Clubs
//first turn you put a clubs on left side of table.
//table(clubs, )
//structure:
        table
      /
    Clubs

Clubs
//second turn you put a clubs on right side of table.
//table(clubs, clubs)
//structure
        table
      /      \
    Clubs   Clubs

Diamond
//third turn you cover a Diamond on left side of Clubs.
//Clubs on left side becomes a left child node of Diamond
//table(Diamond, clubs)
//structure
        table
      /      \
  Diamond   Clubs
    /
 Clubs

Heart
//Fourth turn you cover a Heart on both of side of cards 
//it will be placed on the left side.
//calculate the sum value from left(4) and right(-1) = 3
//table(Heart, )
//structure
            table
            /
         Heart(3+1-1=3)
      /         \
  Diamond(3)   Clubs(-1)
    /
 Clubs(1)


Clubs
//Fifth turn you put a Clubs on right side 
//table=(Heart, Clubs)
//structure
            table
            /    \
         Heart  Clubs
       /      \
  Diamond   Clubs
    /
 Clubs


Heart
//Sixth turn you cover a Heart on both side
//Each of side of card become its child node.
//calculate the sum value from left and right = 7
//table(Heart, )
//structure
                  table
                  /
              Heart(3+3+1+1-1=7)
            /    \
     Heart(3)  Clubs(-1)
       /     \
  Diamond(3) Clubs(1)
    /
 Clubs(1)



Heart
//seventh turn you cannot put Heart because there is only one card on table.
//just ignore this card

Clubs
//eighth turn you put a Clubs on right side 
//table=(Heart, Clubs)
//structure
                  table
                  /    \
              Heart    Clubs
            /    \
       Heart     Clubs
       /     \
  Diamond   Clubs
    /
 Clubs



Diamond
//nineth turn you cover a Diamond on right side of Clubs since the level
//table(Heart, Diamond)
//structure
                  table
                  /    \
              Heart    Diamond
            /    \        \
       Heart    Clubs    Clubs
       /    \
   Diamond   Clubs
    /
  Clubs



Spade
//Endtag, the game is over

• Now you need sum all the Heart value in your tree: 3+7=10

                  table
                  /    \
              Heart(7) Diamond
            /    \        \
       Heart(3)  Clubs    Clubs
       /         \
   Diamond       Clubs
    /
  Clubs

Your output need to be 10\n(\n means a new line)!

Input

Clubs
Clubs
Diamond
Heart
Clubs
Heart
Heart
Clubs
Diamond
Spade

Output

10

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Following an unforeseen enhancement to Wakunda's anti-spy system, professional spy Anya was confronted with a challenge. The anti-spy countermeasures made by Wakunda had made her usual digital spy communication methods nearly infeasible, forcing her to hand-deliver an essential message from Wakunda to her headquarters with the help of her reliable partner, You!

Anya has good memory since she can remember the distance between two places. However, she is not good at math and needs your help to make a program to calculate the shortest-path distance between your current location to a certain location and calculate the distance. Having the shortest-path distance calculation is crucial for this mission to allow both you and Anya to schedule your journey and allocate the necessary supplies. Furthermore, there's no need for concern about remembering the sequence of locations to reach your destination since Anya can assist you spontaneously throughout the journey, both of you only cares about the shortest-path distance to reach your destination from all possible path.

Anya suggests employing Dijkstra’s algorithm to create the shortest-path distance calculator for this mission, which subsequently inspires the operation's name.

Your code should only contain the following library & namespace, you might receive a score deduction if you’re using the other libraries:

#include<iostream>
#include<vector>
#include<stack>
#include<queue>
#include<list>
#include<string.h>
#include<cmath>
using namespace std;

Graph Element

• Node/Vertex: Represent the location

• Edge: Represent the distance between 2 locations

Input

1) Location Insertion

INSERT_LOCATIONS <total_nodes>

<total_nodes> represent the maximum number of location in the test case. For example, if we put this input line:

INSERT_LOCATIONS 100

Then you will have 100 locations of vertex/node starting from ID 1 until 100. Where vertex/node with an ID of 1 is always your location (source)

It’s guaranteed that:

• 2 <= total_nodes <= 100

• 1st vertex/node is always your initial location

 

2) Distance Insertion

INSERT_DISTANCE <location1> <location2> <distance>

For example, we want to connect two locations with ID number 9 and 6, which has a distance of 200:

INSERT_DISTANCE 9 6 200

The previous input line is also equivalent with:

INSERT_DISTANCE 6 9 200

It's guaranteed that:

• Edges consisting of the same pair will not be inserted more than once

• 1 <= location1 <= total number of nodes

• 1 <= location2 <= total number of nodes

• location1 != location2

• <distance> is integer

• 1 <= <distance> <= 10⁵

 

3) Shortest Path Distance Calculation

CALCULATE <destination_id>

The function will generate an output representing the shortest-path distance from your location (ID=1) to your destination. The <destination_id> parameter is the ID of your destinated location.

For example, we use the following input to calculate the distance between your current location (ID=1) to a location with ID = 6

CALCULATE 6

It's guaranteed that:

• 1 < <destination_id> <= <total_nodes>

• This function can be called multiple times in the test case

• This function might be called before we finished all the location/distance insertions

• The shortest path between your location and to destination when this function is called in every test case never consists of an infinite distance (you don’t need to worry if the output distance is infinite).

 

4) Terminate Application

TERMINATE

When the user inputs the terminate command, your application will be ended.

Output

Output must be created immediately when the following "3) Shortest Path Distance Calculation" input was triggered

CALCULATE <destination_id>

The function will generate an output representing the shortest-path distance from your location (ID=1) to your destination. The <destination_id> parameter is the ID of your destinated location.

<the distance of the shortest path> // without newspace in the end of the line
<new line>

For example, we use the following input to calculate the distance between your current location (ID=1) to a location with ID = 6

CALCULATE 6

If the shortest path distance between your location to the node with ID 6 is 900, then the output will be:

900

It's guaranteed that:

• This function can be called multiple times in the test case

• This function might be called before we finished all the location/distance insertions

• The shortest path between your location and to destination when this function is called in every test case never consists of an infinite distance (you don’t need to worry if the output distance is infinite).

 

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

(You are allowed to view this webpage for a slightly better version: https://hackmd.io/@yurisoba/HJr-S8kLh)

Debby loves eating all kind of pastry, she also likes to make long term financial plan to optimize her savings. She would be very happy if you could help her find the most stably-priced type of pastry. As a financial expert, she has devised a way to calculate the stability.

Given n months of price data for m types of pastry, sort the pastries by their price in ascending order for each month, and record their position pm,n (i.e. the cheapest item has p=0).

The volatility of each pastry for each month Vm,i is defined as their position difference relative to the previous month.  Formally:

Find the most stable pastry by minimizing the sum of volatility of each pastry:

Break tie using the order from the original input, the type of pastry that appears first is preferred.

Debby is also an expert in programming and is very nice to give you a short C++ reference which might be useful:

// must compile with c++17 and above
#include <algorithm>
#include <vector>
struct Something {
    int a;
    int b;
};

int main()
{
    std::vector<Something> v;
    // sort a vector, use stable_sort if order has to be persisted
    std::sort(v.begin(), v.end(), [](auto& left, auto& right) {
        return left.a < right.a;
    });
    // vector is now sorted in ascending order
}

Hint: The most stable pastry is the one which its relative price position in each month changes the least.

Input

n m
[m lines x type of pastry (string)]
[n lines x [m x space separated price (unsigned int)]]

 

Output

[1 x type of pastry (string), ended with \n]

 

Sample Input  Download

Sample Output  Download

Tags

Discuss