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

Tags

Discuss