Description

Lantern Festival: Lucky Envelope Activity

You are the organizer attempting to hold the lantern festival, this year. To evoke the happiness and excitement of participants, you prepare an activity called Lucky Envelope. Everyone who entered the festival has a chance to get it.

Because it is a quite huge festival, you divide the whole activity into N places, where N is an integer.

These places are numbered from level 0 to level (N-1). Each place has a ticket station that handles the registration process for incoming families.

Registration Process

Similar to HW1, families must complete a registration process upon arrival:

• The registration takes 2 minutes per family.
• Once registered, families can proceed to the activity area for a chance to receive a lucky envelope.

Ticket Stations & Payment Structure

Each ticket station serves families based on the amount they pay. Each level has a defined payment range and provides a lucky envelope whose total money is calculated as ten times the upper limit of that range.

For N ticket stations:

• Station 0
  • Serves families paying between 1 and 500 dollars
  • Provides a 5000-dollar envelope
• Station 1
  • Serves families paying between 501 and 1000 dollars
  • Provides a 10000-dollar envelope
• … and so on …
• Station (N-1)
  • Serves families paying between 500*(N-1)+1 and 500*N dollars
  • Also serves families paying above 500N dollars [look at Reminder 1]
  • Provides a 5000*N-dollar envelope

Reminder 1:

If a family's payment exceeds the upper limit of the highest level, they are directed to the last station.

Family Information

Each minute, a certain number of families arrive at the festival. Each family is identified by:

• Family Number
• Number of people in the family
• The total money that the family will pay

For example, a family entry may be represented as:

F0, 10, 100 (This is just for the illustration, not for the input format)

Indicating Family 0, consisting of 10 people, and they will pay a total of 100 dollars.

 

Illustration: Case with 3 Ticket Stations (N = 3)

At this moment, 3 families are arriving. F0,10,100 and F1,5,700 and F2,1,800.

• F0 goes to Station 0 (pays 100, within range of 1 to 500)
• F1 goes to Station 2 (pays 1300, within the range of 1001 to 1500)
• F2 goes to Station 2 (pays 1200, within the range of 1001 to 1500)

Now the status at Station 2:

• F1 starts registration (takes 2 minutes).
• F2 waits in line behind F1 since registration is processed one family at a time.

The festival’s registration area is divided into two regions:

1. Registering: Families currently undergoing the registration process at a ticket station.
2. Queuing: Families waiting in line for their turn to register.

Once a family completes registration (meaning they have successfully paid the required money), they can proceed to join the festival and participate in the Lucky Envelope activity.

Special events

1. Suspicious Family

A family is considered suspicious if their average money per person is 10,000 or more

average money per person = The total money they will pay divided by the number of people (using integer division)

Since it is highly unusual for someone to spend 10,000 dollars or more just to attend the festival, such families will be subjected to additional identity verification, including questioning about their source of money like “Who are you?” “Where does your money come from?”.

Special Rule for Suspicious Family:

• The registration time for a suspicious family is doubled, taking 4 minutes instead of 2 minutes.

---

2. Grouping Family

Families arriving at the same time will group together if they meet the following conditions:

1. They arrive at the same minute.
2. They are adjacent in arrival order.
3. They are originally supposed to go to the same ticket station
4. After grouping they can go to the higher level station.

Grouping Effect:

• Their total number of people and total money become the sum of the two original families.
• The two families combine their total money, which may make them go to a higher-level station.
• The grouped family is assigned the family number of the smaller-numbered family.

This rule allows families to upgrade their ticket station and potentially receive a higher-value lucky envelope.

Illustration for grouping: Case with 3 Ticket Stations (N = 3)

Note that

• A grouping family is considered as 1 family.

• Each grouping operation can only group 2 families.

• One family can only group once. Once a family is grouped with a family, they can not group with another.

• If there are multiple ways of grouping, group the family from the front. (once you group a pair of families together, you have to continue to search for other potential pairs of grouping families) 

• Example: F10,4,500 F11,4,500 F12,1,500 F13,1,500

  → Group F10 and F11, forming F10,8,1000

  → Group F12 and F13, forming F12,2,1000

  Instead of Group F11 and F12

• A grouping family can be a suspicious family if it meets the condition of a suspicious family.

• Originally suspicious families also can become unsuspicious, if they don’t meet the condition after grouping.

Lucky Draw Order Rule (After the simulation ends)

After the last minute, for each place families who have entered the festival will participate in the final lucky draw. Although everyone has a chance to win, we assign a specific draw order based on the following rule:

Draw Order Arrangement:

We prioritize families who contribute more payment per person. The arrangement is as follows:

1. First Half – High Contribution Families

   Families whose (payment)-to-(family-size) ratio is equal to or greater than a certain threshold (H) will be placed in the first half of the draw order.

2. Second Half – The Rest

   Families not meeting the above ratio will be placed in the second half.

3. Ordering Within Each Half

   Within each half (first half and second half), families are sorted by their entry order (i.e., the earlier in the front).

Input

First Line

The first line contains three integers N, M, and H separated by a space:

• N is the Number of places (ticket stations).
• M is the total minutes to simulate.
• H is threshold for the arrangement of the draw order

Following M Lines

Each of the next M lines represents the families arriving at that specific minute (from minute 0 to minute M-1).

• Each arriving family is represented by three attributes separated by a comma:
  • Family Number
  • Number of People in the family
  • The total money that the family will pay
• Families arriving at the same minute are separated by a space.
• If no family arrives at a particular minute, the line contains just “0”.

Example: 0,1,90 1,1,90 2,2,300 3,3,200

Input Constraint:

• There are no duplicate Family Numbers during all the time
• 0 < N ≤ 50
• 0 < M ≤ 500
• 0 < H ≤ 1000
• Number of families arriving every minute ≤ 100

Here is a reference code in C++ that may help you parse the family line. 

You can also write your own code 

//if you attempt to use please include these headers
#include <vector>
#include <sstream>
#include <iomanip>

string line;
getline(cin, line);
if (line != "0") { // Process only non-zero lines
    stringstream line_stream(line);  
    string famData;

    // line: 0,1,1 1,1,1 2,2,2
    while (line_stream >> famData) { // Split by spaces (each family)
			
        stringstream family_stream(famData);
        string temp;
        vector<int> values; //will include number, #people, money

        while (getline(family_stream, temp, ',')) { // Split by commas
            values.push_back(stoi(temp));
        }

        if (values.size() == 3) { // Ensure valid data
            /*
            //testing the input
            cout<<"Family info:"<<"\n";
            cout<<"Family number:"<<values[0]<<"\n"; 
            cout<<"number of people:"<<values[1]<<"\n";
            cout<<"money:"<<values[2]<<"\n";
            */
                    
            /*
            maybe some additional code here
            */
        }	
        /*
        maybe some additional code here
        */	
    }
}

Output

For each place (ticket station), display the following information:

• Place ID

• Comparing the total money collected to the envelope you will give for the place. Show if the place

  • Make profit , followed by how much profit you make for the place.

  • Lose money, followed by how much money you lose for the place.

  • Break even

• List the families currently queuing (frontmost family at the top).

  • Each entry includes:
    • Family Number followed by the Number of People and the money they pay
    • If no family is queuing, keep the section title but do not output the family lines.

• Show the family currently undergoing registration.

  • This entry includes:
    • Family Number followed by the Number of People and the money they pay
    • If no family is registering, keep the section title but do not output the family lines.

• List families that have completed registration (entered the place), in reverse order (most recent entry at the top).

  • Each entry includes:
    • Family Number followed by the Number of People and the money they pay
    • If no family is entered, keep the section title but not output the family lines.

• Show the draw order of the place with their Family Numbers.

  Example: Draw order: 3 4 5 0 1 2 (there is a space at the end of the line) 

Use a new line to separate each place’s output.

Ensure there is a new line at the end of the entire output.

Sample Input  Download

Sample Output  Download

Discuss

Description

With the success of Spiderfy after a mere few weeks, a new major update is planned for the application. Being the lead developer of the application’s launch, you are now tasked with implementing a Play Queue function into the app. This function will allow users to queue up their favorite songs and play them. There are many commands that users want and it is your job to implement it.

Welcome to ‘Spiderfy Streaming Service: Project Q’!

You need to implement a list of songs that repeats itself. At first the list of songs is empty but through certain commands the user can transform the list to their preferences.

Commands:

ADD_SONG N d i
Add a song with the name N and duration d (in seconds) to the list of songs at index i. The list index starts at 0. There is a chance that users may input a value i that exceeds the length of the list, in this case just add the song to the end of the list. 

DELETE_SONG N
Delete a song with the name N. Locate a song based on their name and remove them from the list. If the song does not exist in the list, print out: “Song not found”. 

SKIP S
Move S number of songs from the front of the list to the back of the list.

REVERSE
Reverse the position of all the songs. 

PLAY t
Play the list of songs for t seconds. After t seconds has passed, print out the current playing song. Remember that the list of songs loops to itself. Print it as: “Currently playing: [song name]”.

DISPLAY
Print out “Playlist Contents:” followed by the list of songs and their duration in the playlist preceded by a “>”. If the playlist is empty, print "Playlist Contents" followed up with “-- empty --” at the next line. After printing the list of songs, regardless if the playlist is empty, print out "Playlist Duration: [total playlist duration] seconds”. (total playlist duration is set to 0 if the list of songs is empty).

Testcase Difficulty
Testcase 1: Adding and Removing Songs
Testcase 2: Adding and Removing Songs + Skip Function
Testcase 3: Adding and Removing Songs + Skip Function + ReverseFunction
Testcase 4: Adding and Removing Songs + Play Function
Testcase 5: Adding and Removing Songs + Play Function

Input

The input consists of the aforementioned list of commands:
- ADD_SONG N d i
- DELETE_SONG N
- SKIP S
- REVERSE
- PLAY t
- DISPLAY

You must do these commands until EOF. Parameter Constraints:
 

Parameter	Parameter Type	Size
N	string	1 <= len(N) <=100
d	int	1 <= d <= 300
i	int	1 <= i <= 10,000
S	int	1 <= S <= 10,000
t	int	1 <= t <= 10^9

 

Output

Print the outputs required according to each command. Enter a newline after every output unless specified otherwise. 

Sample Input  Download

Sample Output  Download

Discuss

Description

Introduction

In international trade, governments frequently adjust tariff policies for different countries. These policy changes need to be accurately recorded and tracked so that the tariff status for any specific country can be queried at any point in time. This assignment requires the design of a tariff policy tracking system, similar to a version control system.

 

Problem Description

In this assignment, we will design a simple tariff policy tracking system. We need to implement three main functions: 

Announce (announce a new policy), 

Switch (switch to the policy of a specific date), 

Check (check the current tariff rate of a specific country), 

The system starts with an empty root node, and all countries initially have no tariffs.

 

1. Announce (Announce a new policy)

Command format:

This command creates a new policy node containing tariff changes for <country_count> countries. Each country's tariff change includes the country name and the new tariff rate. The new policy node becomes a child of the current node, and the current node is updated to this new node.

The system should output:

New policy announced on <date>

 

2. Switch (Switch to a policy on a specific date)

Command format:

This command switches the current node to the policy node of the specified date.

If a policy is found for the given date, output:

Switched to Policy on <date>
And the current node will change

If not found, output:
No policy found on <date>
And the current node will not change

After doing a switch, the current_node of the tree will change to the target of the switch, and if an announce is performed afterward, the new node should connect after the current_node. However, don't worry, the test cases ensure that after a switch, if an announce will be performed, it will first switch back to the leaf node of the tree.

 

3. Check (Check the tariff history of a specific country)

Command format:

If history is found, output in the format:

Tariff history for <country_name>:

<rate_1>

<rate_2>

…

 

If no tariff policy is found, output:

No tariff policy for <country_name>

 

System Structure

We provide the TradePolicy, TariffPolicy and PolicyNode classes. Each PolicyNode is designed to store information for a single policy announcement.

 

The TariffPolicy class uses a Trie data structure to optimize country name lookup performance.

 

Implementing the Trie is necessary to ensure efficient data retrieval, especially for the check command.

 

Test Cases

Case 1 : Announce & Check

Case 2 : Announce & Check

Case 3 : Announce & Switch & Check

Case 4 : Announce & Switch & Check

Case 5 : Announce & Switch & Check

Input

The input will contain N commands, each representing one of the three operations described above.

Input parameter ranges:

1. 1 ≤ N ≤ 5 * 10^5

2. Country names contain only lowercase letters, with 1 ≤ len(country_name) ≤ 20

3. Tariff rate format is a percentage, such as "25%" or "10.5%"

4. Date format is "YYYY-MM-DD"

5. Please submit your solution in C++11.

6. This is a partially graded assignment, so you do not need to worry about the exact input/output format.

7. You are required to implement the following functions:

Output

Print output required according to each command. Enter a newline after every output.

Sample Input  Download

Sample Output  Download

Partial Judge Code

14638.cpp

Partial Judge Header

14638.h

Discuss

Description

Metro Meet-Up: Find the Fastest Station to Gather

Didier and his friends are exploring Taipei by metro, starting from different stations. They’ve agreed to spend the day together, but every extra minute spent riding separately is one less minute they can enjoy sightseeing, taking photos, and eating street food as a group. So, they’d like to choose a single meeting station that minimizes the total travel time for everyone combined.

You have exclusive access to the metro’s live timetable: a list of every direct ride between adjacent stations, its travel time, and the line it belongs to. With this information, and knowing that switching from one line to another always adds a fixed transfer penalty, you can compute the optimal meeting point and the best route for each friend.

The metro map is a graph:

• Node = station.
• Edge = direct ride between two adjacent stations on the same line.
• Each edge has
  • an integer ride-time (in minutes) and
  • a line-name (e.g., Red, Blue).

Whenever a passenger changes from one line to another at a station, a fixed transfer-penalty P minutes is added to their personal travel time.

Note: The first line they board does not incur a penalty.

Your task is to decide:

1. Which station everyone should meet at.
2. The individual route each friend should take.

At the end the total travel time (ride times + transfer penalties for all friends) should be minimized.

At least one station is reachable from every start station.

For this task a subset of stations has been selected from 6 of the lines, making a total of 77 stations (unique nodes) that ensure it contains all possible transfer stations between themselves. The transfer stations are marked with the two colors corresponding to the lines they connect. You can check them in the following table:

The following is a render of the resulting network graph from the subset of stations:

Note: The network graph does not correspond to the actual physical locations in the map, it just shows how the nodes are connected in between. Use this only as a reference, the input will be based in the structure of this network graph, you do not need to code all of this information.

 

Clarifications:

• Changing direction but staying on the same line at a station does not count as a transfer.
• There will always be one correct answer.
• Tie-break rule
  • When two stations give the same group total, compare the friends one by one, in input order:
    • Let’s say there are two candidate stations, if friend #1 needs less time to reach Station A than Station B, choose Station A.
    • If their times are equal, move on to friend #2, and so forth.
  • The first friend whose travel times differ decides the winner.

 

Test Cases (return here after reading all the quiz info):

1. Two friends, no transfer, order of friends matter.
2. Four friends, no transfer, order of friends matter.
3. Three friends, no transfer, unique solution.
4. Four friends, no transfer, unique solution.
5. Five friends, some transfer, all stations’ connections in the input, unique solution.

 

Input

First line:

m f P

• m - number of connections (edges) (1 ≤ m ≤ 88)
• f - number of friends (2 ≤ f ≤ 5)
• P - transfer penalty in minutes (1≤ P ≤ 20)

Assume the system will not always show the complete timetable with all station nodes, so the number of connections will vary from 1 to 88. The number 88 refers to the max number of edges with the 77 station nodes shown.

 

Next m lines describe each station’s connection:

from  to  time  lineName

• from, to - station names (strings without spaces, ≤ 256 chars)
• time - ride time in minutes (1 ≤ time ≤ 20)
• lineName - name of the line (string without spaces)

Note: Connections are bidirectional, which means you can ride both ways with the same time.

 

Next f lines are the boarding station of each friend:

friend_1_starting_station

…

friend_f_starting_station

 

Example 1 – Simple meet-up.

Input

3 2 4

Jiantan Yuanshan 4 Red

Yuanshan Minquan_W_Rd 3 Red

Daqiaotou Minquan_W_Rd 2 Orange

Jiantan

Daqiaotou

 

Example 2 – Transfer counts!

Input

13 2 4

Jiantan Yuanshan 3 Red

Yuanshan Minquan_W_Rd 2 Red

Minquan_W_Rd Shuanglian 2 Red

Shuanglian Zhongshan 2 Red

Zhongshan Taipei_Main_Station 2 Red

Taipei_Main_Station Shandao_Temple 3 Blue

Shandao_Temple Zhongxiao_Xinsheng 2 Blue

Zhongxiao_Xinsheng Zhongxiao_Fuxing 2 Blue

Jiannan_Rd Dazhi 3 Brown

Dazhi Songshan_Airport 2 Brown

Songshan_Airport Zhongshan_Junior_HS 3 Brown

Zhongshan_Junior_HS Nanjing_Fuxing 2 Brown

Nanjing_Fuxing Zhongxiao_Fuxing 2 Brown

Jiantan

Jiannan_Rd

 

Output

Lines in order:

minimal-total-time

meeting-station

route-1

...

route-f

1. minimal-total-time - the minimal sum of travel times (minutes) for all friends.
2. meeting-station - the chosen meeting station.
3. Following f lines (routes) - each friend’s path as
   Start->…->Meeting, using "->" between station names, without blank spaces, in the same order that their start stations were given.

 

Example 1 – Simple meet-up.

Output

• 9
• Minquan_W_Rd
• Jiantan->Yuanshan->Minquan_W_Rd
• Daqiaotou->Minquan_W_Rd

Explanation

Transfer penalty P = 4 minutes. In this case the best route did not require transferring, so it’s not needed.

No. Friend	Friend Starting Point	Route	Ride time	Transfers	Penalty	Personal total
1	Jiantan	Jiantan->Yuanshan->Minquan_W_Rd	4+3 = 7	0	0	7
2	Daqiaotou	Daqiaotou->Minquan_W_Rd	2	0	0	2
Total						9

 

Meeting anywhere else costs more because of the transfer penalty, so Minquan_W_Rd is the best option.

 

Example 2 – Transfer counts!

Output

• 34
• Taipei_Main_Station
• Jiantan->Yuanshan->Minquan_W_Rd->Shuanglian->Zhongshan->Taipei_Main_Station
• Jiannan_Rd->Dazhi->Songshan_Airport->Zhongshan_Junior_HS->Nanjing_Fuxing-> Zhongxiao_Fuxing->Zhongxiao_Xinsheng->Shandao_Temple->Taipei_Main_Station

 

Explanation

Transfer penalty P = 4 minutes.

There are two candidate meet-up stations with the same minimal total time to get there for the total group of friends. We optimize on the minimum of each friend’s time from top to bottom from the provided input.

Station	Friend #1 (Jiantan)	Friend #2 (Jiannan_Rd)	Group Total	Profile
Taipei_Main_Station	11 min	23 min	34	(34, 11, 23)
Zhongxiao_Fuxing	22 min	12 min	34	(34, 22, 12)

 

Because we are looking at the friend’s list in order, then the selected meet-up station is Taipei_Main_Station, because Friend #1 has the minimum time to travel to that station compared to the other candidate (check the tie-break-rule in the Clarifications section).

 

So the result can be viewed like this:

No. Friend	Friend Starting Point	Route	Ride time	Transfers	Penalty	Personal total
1	Jiantan	Red to Taipei_Main_Station	11	0	0	11
2	Jiannan_Rd	Brown to Zhongxiao_Fuxing -> Blue to Taipei_Main_Station	12 + 7 = 19	1	4	23
Total						34

 

Sample Input  Download

Sample Output  Download

Discuss