2019 ICPC NENA (Quebec) Regional Qualifier

Start

2019-10-26 05:00 AKDT

2019 ICPC NENA (Quebec) Regional Qualifier

End

2019-10-26 11:00 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -224 days 14:17:29

Time elapsed

6:00:00

Time remaining

0:00:00

Problem D
3D Food Maker

Similar to a $3$D printer we have a device that prepares food. The device takes a recipe as a set of operations (i.e., LOAD, ADD, MIX, SPRINKL, GRATE, and BAKE) forming a single line of cook code. For example, one valid cook code would be:

( tomato ADD ( onion MIX parsley ) )

Your code should convert cook code into a set of instructions for the food maker with one instruction per line. The order of operations is depicted using parentheses in the cook code, and the generated instructions should preserve that order. In the previous example, the first operation in the output should be the innermost operation which is “MIX” and after that the operation “ADD” is processed. When two operations of equal priority are possible, the one on the left must be evaluated first. Here is an example of that where the operation ( milk MIX butter ) should be evaluated before ( onion MIX parsley ):

( ( milk MIX butter ) ADD ( onion MIX parsley ) )

Input

The cook code is a fully-parenthesized single line with two food items surrounding each operation. (As in the example above, there are two spaces surrounding every token). Your code can expect the following operations: LOAD, ADD, MIX, SPRINKL, GRATE, and BAKE. Also, your code should expect any set of food items (e.g., egg, beef, chicken, rice, etc.) which are single words given in lowercase letters (hence operations can not take the place of a food item). Below is a description of the operations and the operands they take:

LOAD item :loads a food item into the operation area of the food maker.

ADD item :adds item to whatever is in the operation area in the food maker.

MIX item :mixes item with whatever is in the operation area in the food maker.

SPRINKL item :sprinkles item on top of whatever is in the operation area in the food maker.

GRATE item :grates item on top of whatever is in the operation area in the food maker.

BAKE item :bakes item, as a final step in every recipe.

Output

The output should be formatted as one instruction per line, as in the sample output below. The food maker can LOAD a food item into the device, ADD/MIX/SPRINKL/GRATE whatever is loaded with another food item, STORE results in a specific bowl, and bake the contents of a specific bowl. The food maker has loading space for only one item in the device, and therefore any other item must be stored in a bowl. Luckily, the device can utilize an infinite number of bowls for storing items, yet the available bowl with the smallest number should always be used. A bowl can be used as an item for a subsequent operation like “bowl_$2$” on the line LOAD bowl_2 in Sample Output $2$ below. For contamination purposes, a bowl can not be reused to store items more than once. Also, since the food maker cleans the operating surface every time the STORE command is used, no instructions should be reduced to make the process more efficient. As a general rule, instructions should not be reduced for efficiency. An example of this situation would be a STORE bowl_1 instruction followed by LOAD bowl_1, these instructions should not be reduced for efficiency to prioritize hygiene. In addition, each set of instructions ends with baking the last outcome which is the last bowl.

Sample Input 1 Sample Output 1
( tomato ADD ( onion MIX parsley ) )
LOAD       onion
MIX     parsley
STORE   bowl_1
LOAD    tomato
ADD     bowl_1
STORE   bowl_2
BAKE    bowl_2
Sample Input 2 Sample Output 2
( ( beef ADD ( egg MIX oil ) ) ADD ( tomato ADD ( onion MIX parsley ) ) )
LOAD       egg
MIX     oil
STORE   bowl_1
LOAD    beef
ADD     bowl_1
STORE   bowl_2
LOAD    onion
MIX     parsley
STORE   bowl_3
LOAD    tomato
ADD     bowl_3
STORE   bowl_4
LOAD    bowl_2
ADD     bowl_4
STORE   bowl_5
BAKE    bowl_5