| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 14584 | Lantern Festival |
|
Description
Lantern Festival
Background
In 2025, Taiwan is set to light up with a series of amazing lantern festivals that will turn the night sky into a breathtaking display of colors. From busy city streets to charming rural spots, families and friends will come together to celebrate this cherished tradition. Sure, there might be long lines and lots of traffic, but that's all part of the adventure, a shared experience that makes every glowing lantern a symbol of hope, unity, and pure joy.
Explanation
In the beginning, you are given the places where the lantern festival will be held and the sequence of people queuing in each place. Every minute, you receive the number of families arriving with their total ticket prices (these prices depend on the package and benefits they will have inside the venue). When a family comes and if there is no one in front of them, they go directly to the cashier to buy their tickets and register. Each family spends two minutes at the cashier before entering the festival. If a family arrives and another family is already waiting or being processed in front of them, they must queue behind that family. Whenever the family in front moves forward by one step, the next family also moves one step forward or proceeds to the cashier if there is no one ahead.
Example (based on the input, you may check the input) :
Quit
There is also a time limit for waiting in the queue. If a family has waited for at least 60 minutes and is at the end of the queue, they will give up waiting and leave. In addition, if the family in front of them is not initially at the end of the queue but becomes the last family after the one behind them quits, that newly last family will also leave if it has been waiting at least 60 minutes. Because there is no one blocking them anymore, and they have been waiting for so long, they decide to quit as well.
However, these quitting rules do not apply to families that are under the register process, families within the no-quit zone, Go Go families, and families that have received a special offer (as explained further in the special occasions section).
Special Occasions
- No Quit Zone
When a family is among the first X positions behind the registration region (registration region is not included in X positions), they will not quit regardless of how long they have been waiting. One family, regardless of how many people are inside it, will take one position. The value of X is provided in the test case. Note that a family currently undergoing the 2-minute registration process is not considered when counting the No Quit Zone, start counting 1 from the family behind them (The family in the registration would still be considered as a queuing family when computing the number of queuing people in the output summary). This no-quit zone exists because families close to entering the venue tend to remain optimistic about attending the festival event.
Example when X is 4 :
- Go Go Family
Those families consisting of at least 100 people are defined as the Go Go family. They are very determined to attend the festival, even if they do not receive the special offer. When a Go Go Family is queuing, whether at the end or anywhere in the line, the family directly in front of them (if that family is not a Go Go Family) may leave the queue if they have been waiting for at least 60 minutes. In other words, Go Go Families does not block other families from quitting because they are eager to enter the festival and are willing to let others go if it means they can get through faster.
- Special Offer
If there exist consecutive families whose sum of their price is just equal to Y, the family right after them can get a special offer. The family who obtains a special offer (called Special family), regardless of their ticket price, receives free admission. Moreover, Special families will never quit the queue and will prevent the families in front of them from leaving. This is because every family monitors the total amount of money required from the families ahead, so they know they can get the special offer. A Go Go Family will automatically become a Special Family when they realize they are eligible for free tickets.
Additionally, only at most one family can have a special offer at any moment. If there are multiple families also satisfy the condition at the same time, the first one will receive the special offer. The next possible special family will be determined until the previous special family enters the festival.
Example (in these given examples, will be given the price of each family)
Ex1:
Special offer Y = 20
17, 13, 7, 4, 5
The next family that will get the special offer is the family that pays 4. Because 13+7 is exactly 20. The family that pays 7 will not get a special offer because the family before them has the accumulation of 17+13=30 which is more than 20, not exactly 20.
Ex2:
Special offer Y = 20
12, 20, 5, 5, 5, 5, 7
Only the 3rd family will get a special offer. The 7th family will not because the 3rd family will hold the special offer until it enters into the festival.
Ex3:
Special offer Y = 20
15, 5, 15, 5, 15, 5
The 3rd family will receive a special offer. Then the 6th family will receive the special offer after the 3rd family finishes the registration and enters into the festival.
You must follow the Update Priority Flow below when you update the state every new minute
- Check the registration process. If it has finished, let the registration family enter the festival, and everyone behind moves a step forward
- Release the quitting families
- Add the new coming families
Summary and Hints
Consider the behavior of families in different zones: registration region, no-quit zone, and the zone where people will quit.
Consider the behavior of different types of families: general family, Go Go family, and Special family.
Some families will block the family ahead of them from quitting and some families will not (check the description above).
Input
STL related to Data Structures (such as vector, stack, queue, deque, map, unordered_map, set, unordered_set, priority_queue, etc.) are not allowed.
All other STL libraries can be used.
In the first line, there will be 4 variables F, X, Y, and M (separated by a space).
F determines the number of places where the festival is being held.
X is the length of No Quit Zone as described above.
Y is the amount of money to determine which families will get the special offer.
M is the number of minutes to simulate.
The next F line will determine how many families are queuing and the price that they need to pay per place initially (minute zero).
The format would be A,P A,P A,P A,P …. A,P where A is the total number of people in a family and P is the price that they need to pay. The total number of A,P will be undecided and ranging from 1 to 100000. If a place does not have any family coming, the input for that place would be 0.
The next (FxM+M) lines would be the next family that would enter each place, each minute, there would be an update of how many families had just started to queue at a certain place, and each minute update would be separated by a newline.
Note :
When there is no special offer, Y is defined by -1.
Y ranged from -1 until 1000000
X ranged from 0 until 1000000
F ranged from 1 until 1000000
M ranged from 1 until 1000000
Input format:
[how many places] [X] [Y] [how many minutes will pass by]
[..] a total of people, price they pay
0 means no one there
(the next line is updating how many families come in different places)
(the next minute)
[..]
(the next minute)
[..]
(the next minute)
[..]
…
Output
Gives the total money for each place
The total number of people who entered to the festival in each place
The total number of people quit in each place
The total of current people queuing (including the people in registration, no quit zone, and quit zone) in each place
The Families that have entered the place (from the most recent one to the oldest record). Show the Family ID and the number of people in the family. Each family will have an ID once they enter the queue, the first family that gets into the queue will have ID 1, the second family will have ID 2, the 10th family will have ID 10, and so on. Each family will have a unique ID in each place that they are queuing.
Note that there is a space between "Entered Family" and ":"
Do not forget to give a newline after the last output.