Time Limit: 2 Seconds
Memory Limit: 65536 KB
An excellent online judge administrator means a genius special judge factory!! who produces batch judge scripts day and night.
For most programming problems, you can just compare the programmer's output against the correct answer, and if they are literally the same, the programmer's output is correct, otherwise it's wrong. But for some problems, there may be many correct answers and they can be different from each other literally. So the administrator must write a program, which is named "Special Judge", to verify programmers' output.
Now you will become one day administrator of our online judge, and the only task is to write a special judge for the following problem. Maybe you will find it very very boring, but just have a try!
Here is the description of the original problem
/* Adapted from "Chandelier", Northeastern Europe 2004 */
Lamps-O-Matic company assembles very large chandeliers. A chandelier consists of multiple levels. On the first level crystal pendants are attached to the rings. Assembled rings and new pendants are attached to the rings of the next level, and so on. At the end there is a single large ring --- the complete chandelier with multiple smaller rings and pendants hanging from it.
A special-purpose robot assembles chandeliers. It has a supply of crystal pendants and empty rings, and a stack to store elements of a chandelier during assembly. Initially the stack is empty. Robot executes a list of commands to assemble a chandelier.
On command "a" robot takes a new crystal pendant and places it on the top of the stack. On command "1" to "9" robot takes the corresponding number of items from the top of the stack and consecutively attaches them to the new ring. The newly assembled ring is then placed on the top of the stack. At the end of the program there is a single item on the stack --- the complete chandelier.
Unfortunately, for some programs it turns out that the stack during their execution needs to store too many items at some moments. Your task is to optimize the given program, so that the overall design of the respective chandelier remains the same, but the maximal number of items on the stack during the execution is minimal. A pendant or any complex multi-level assembled ring count as a single item of the stack.
The design of a chandelier is considered to be the same if each ring contains the same items in the same order. Since rings are circular it does not matter what item is on the top of the stack when the robot receives a command to assemble a new ring, but the relative order of the items on the stack is important.
For example, if the robot receives command "4" when items <i1 , i2 , i3 , i4 > are on the top of the stack in this order (i1 being the topmost), then the same ring is also assembled if these items are arranged on the stack in the following ways: <i2 , i3 , i4 , i1 >, or <i3 , i4 , i1 , i2 >, or <i4 , i1 , i2 , i3 >.
There are several test cases in the input. Each case contains a single line with a valid program for the robot. The program consists of at most 10,000 characters.
On the first line of the output file write the minimal required stack capacity (number of items it can hold) to assemble the chandelier. On the second line write some program for the assembly robot that uses stack of this capacity and results in the same chandelier.
Remember now you are judgment, not a competitor, so "The minimal required stack capacity (number of items it can hold) to assemble the chandelier" will be told by the author of this problem. I am quite sure this information will be significant for you to finish this mission.
There are several test cases in the input.
Each case contains three parts, the standard input of the original problem, the minimal required stack capacity to assemble the chandelier and the output of user solution.
The first line of each case is the standard input, a valid program for the robot. The program consists of at most 10,000 characters. The second line is a single integer which indicates the minimal required stack capacity to assemble the chandelier, and the last line is the user's output, you can assume that the user's output is a string not more than 10,000 characters without any space. Another assumption is that in this problem we DO NOT require the user specify the stack capacity of his solution, because we treat it as redundancy, you can easily calculate it from the program.
A single line for each test case. If the user's program is invalid, which means the robot could not assemble the original chandelier by this program, output "Wrong Answer -- Invalid program", and if the solution is valid, but not optimal, which means it needs more stack capacity than requirement, output "Wrong Answer -- Not optimal", otherwise it means the user's output is accurate, then output "Accepted".
Wrong Answer -- Not optimal
Wrong Answer -- Invalid program
Author: LIU, Yaoting
Source: Zhejiang University Local Contest 2006