ZOJ Problem Set - 2444
Outel, a famous semiconductor company, released recently a new model of microprocessor called Platinium. Like many modern processors, Platinium can execute many instructions in one clock step providing that there are no dependencies between them (instruction I2 is dependent on instruction I1 if for example I2 reads a register that I1 writes to). Some processors are so clever that they calculate on the fly which instructions can be safely executed in parallel. Platinium however expects this information to be explicitly specified. A special marker, called simply a stop, inserted between two instructions indicates that some instructions after the stop are possibly dependent on some instructions before the stop. In other words instructions between two successive stops can be executed in parallel and there should not be dependencies between them.
Another interesting feature of Platinium is that a sequence of instructions must be split into groups of one, two or three successive instructions. Each group has to be packed into a container called a bundle. Each bundle has 3 slots and a single instruction can be put into each slot, however some slots may stay empty. Each instruction is categorized into one of 10 instruction types denoted by consecutive capital letters from A to J (instructions of the same type have silimar functionality, for example type A groups integer arithmetic instructions and type F groups floating-point instructions). Only instructions of certain types are allowed to be packed into one bundle. A template specifies one permissible combination of instruction types within a bundle. A template can also specify a position of a stop in the middle of a bundle (there is at most one such stop allowed). In addition, stops are allowed between any two adjoining bundles. A set of templates is called a bundling profile. When packing instructions into bundles, one has to use templates from bundling profile only.
Although Platinium is equipped with an instruction cache it was found that for maximal performance it is most crucial to pack instructions as densely as possible. Second important thing is to use a small number of stops.
Your task is to write a program for bundling Platinium instructions. For the sake of simplicity we assume that the instructions cannot be reordered.
Write a program that:
The input consists of several test cases.
For each test case, print in one line two integers B and S separated by a single space. Integer B is the minimal number of bundles in a valid packing. Integer S is the minimal number of all stops that are required for the minimal number of bundles.
4 9 ABB 0 BAD 1 AAB 0 ABB 2 B 0 B 1 A 1 A 1 B 4 D 0 A 0 B 3 B 0
Output for the Sample Input
Source: Central Europe 2003