26348번 - Safely Stacking Leftover Pizzas 다국어

Rafael and his roommates love pizza, but they are on a budget, so they have decided to eat the same exact amount of pizza every day for the semester — up to 100 days in a row. Starting on the first day of the semester, they will order a few different kinds of cheap-but-tasty pizza from Ultracheap Pizza Express — perhaps a Pepperoni, a Sausage & Mushroom, and a Veggie. The store is too cheap to slice the pizzas, so Rafael will slice each one based on their plan: maybe cutting the Pepperoni pie into 8 slices, the Sausage into 7, and the Veggie into 11. Then they will enjoy some fresh hot slices — altogether consuming, for example: 1 Pepperoni, 1 Sausage, and 2 Veggie slices. Finally they will stack the leftover pizzas, in their original boxes, inside their cheap-but-cold refrigerator, which has no shelves. The tiny refrigerator is big enough for only one stack of pizzas and not several separate stacks.

On each day thereafter, they will pull out the entire stack from the refrigerator, open the boxes, and eat the exact same number of slices from each pizza that they had decided on the first day — either cold, or nuked in their cheap-but-warm microwave. After the slices are eaten each day, any leftover pizzas are placed back in the refrigerator, and stacked in the same exact order as they were before. Why this meticulous stacking? Ultracheap doesn’t label the boxes, so keeping consistent order is the only way to tell the pizzas apart without constantly re-opening them.

When a pizza is nearly finished, they will order a replacement for it that arrives just in time such that the amount of each type of pizza consumed each day is always exactly the same. The new, whole pizzas only show up right before the slices are consumed for the day, so there is never a “leftover” whole pizza in the refrigerator and there is never insufficient pizza. Empty boxes are not leftovers either — they go in the trash. But even though sometimes there are no leftovers of a particular kind of pizza, the remaining pizzas will still be stacked in the same relative order as on the first day. For example, if the stacking order is Veggie on top, then Pepperoni, then Sausage on the bottom, and the Pepperoni box is empty when it's time to put away the leftovers, then the Veggie box will be stacked directly onto the Sausage box. On the next day when a new box of Pepperoni arrives, the three boxes will again maintain the first-day ordering.

One problem with stacking: well, those cardboard boxes are ultra-cheap. Nothing ruins a pizza like having its cardboard box collapse onto it. Cardboard-flavored mozzarella...Yecch!

Rafael came up with the bright idea to stack the boxes lightest to heaviest, with the heaviest leftover pie on the bottom, to reduce the chance of one pizza crushing another. Since all the pizzas weigh the same initially, he can predict the weight of the leftovers by calculating the fraction of the pie that remains in the box. Given the example above, on the first day there will be the following leftovers: 7/8 Pepperoni, 6/7 Sausage, and 9/11 Veggie, so they should be stacked with Pepperoni on the bottom, then Sausage, with Veggie on top.

Roommate Robin points out that Rafael’s plan works fine on the first day, but different pizzas get consumed at different rates. So by always stacking leftover pizzas in the same order, it is possible for a heavier pizza to be stacked on top of a lighter one, risking a ruined pie. Continuing the previous example, on the 6th day, the following leftovers would need to be stacked: 2/8 Pepperoni, 1/7 Sausage, and 10/11 Veggie (having eaten 1 leftover slice and 1 fresh slice to get the required 2 slices). The Pepperoni leftovers are properly under the lighter Sausage, but the Veggie pie is on top, even though it’s now the heaviest! This puts the Sausage leftovers at risk.

Given the list of pizzas ordered and the rates at which they are consumed, determine a stacking order for the leftover pizzas that can be used every day but will minimize the chance of a cardboard cheese catastrophe.

The first line of input consists of a positive integer, N, indicating the number of semester plans to evaluate. Each semester plan starts with a line that contains an integer P (2 ≤ P ≤ 5), which is the total number of pizzas that will be ordered the first day, followed by a space, followed by an integer D (1 ≤ D ≤ 100), which is the duration of the plan in days, since Rafael might give up on pizza and go on a Paleo diet. The next 2×P lines will describe each pizza, in exactly 2 lines each.

The first line of each pizza description will consist of 1 to 20 lower-case letters naming the type of pizza. Names will be unique within each semester plan. The second line will consist of exactly two integers E (1 ≤ E < 20) and S (E < S ≤ 20), separated by a space, where E is the number of slices eaten from that type of pizza each day, and S is the total number of slices in a whole pizza of that type. There are no blank lines or extra spaces in the input.

For each semester plan in the input, output a line “Leftover Pizza Stacking Order for Semester M:” where M is the number of the semester plan in the input, counting from 1. Starting on the next output line, print the P names of the pizza types for that semester plan, one per line, in order that they should be stacked, from top to bottom. The stacking order must be the safest possible one — that is, it must minimize the number of instances over D days in which a heavier pizza is stacked immediately above a lighter pizza; note that multiple such instances are possible in the same stack on the same day and each instance counts towards the total; also note that the stacking after the final day must be checked as well and counted towards the total.

If there is more than one safest stacking, output the order that would be first alphabetically, when comparing pizza names from top to bottom of the stacks. Leave one blank line after the output for each semester plan. Follow the format illustrated in Sample Output.