시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 0 | 0 | 0 | 0.000% |
A manager for a toy company wants to reduce the cost of manufacturing their line of toys. Briefly, the toys are created by robots that operate on assembly tracks by adding and linking track components into modules and by merging existing modules into more complex modules. Components can be either active or inactive. At any moment there is exactly one active component per each module and track; and this is the only component that can be linked or merged on that track for that module.
The new budget for this company will only support components which consist of three colors and adjacent components must have different colors. Your job is to decide which of the current toys in the inventory can be produced with this coloring limitation.
The company uses the following BNF formalism to describe more precisely the blueprints of its toys:
(
’ <operator-sequence> ‘)
’
(
’ <module>1<module>2 ‘)
’
(
’ <merged-module><operator-sequence> ‘)
’
The following examples show several simple toy blueprints; in the figures tracks are represented as horizontal dotted lines, components as circles, links as full lines, and the time axis flows from left to right.
Example 1 Figure 4 depicts a 3-colorable toy that can be built using the following blueprint:
2 ( 20 10 21 2 20 )
Figure 4: 3-colorable toy
There are 3 tracks numbered 0, 1, 2. The toy consists of a single module containing 4 components labeled a, b, c, d, linked by the lines c–a, b–a, c–b, d–a. To build this toy the robot will execute in order the following operations:
Note that the same toy can also be built using several other blueprints, such as the following two:
2 ( 10 20 21 2 20 ) 2 ( ( ( 20 10 ) ( 21 ) ) 2 20 )
Example 2 Figures 5 and 6 illustrate a sequence of operations involving a merge, for another 3-colorable (in fact even 2-colorable) toy that can be built as specified by the following blueprint:
1 ( ( ( 10 1 10 0 ) ( 10 1 10 0 ) ) 10 1 10 )
Figure 5: Modules to be merged
Figure 6: Resulting toy
The input will consist of a sequence of toy blueprints, one per line of at most 250 characters. Each toy blueprint contains a sequence of tokens separated by single spaces, and conforming to the BNF rules stated earlier.
The first token is a positive integer t, 0 ≤ t ≤ 6, denoting the maximum track number for the robot’s arms to grab (i.e., there are t + 1 current components for the robot).
The interpretations for the remaining tokens are given in the next table.
Token | Meaning of the Robot’s Instruction |
---|---|
i | Add a new component on track i, where i is a decimal digit, 0 ≤ i ≤ t. Note that this component becomes the active component on this track. |
ij | Link the active components on tracks i and j, where i and j are decimal digits, t ≥ i > j ≥ 0. Note this token consists of two track numbers, with no intervening space. |
( |
Begin marker for a new module. Note that, according to the BNF description two tokens ‘) ’ and ‘( ’ adjacent in sequence denote a merge operation. |
) |
End marker for a new module. |
The input will be terminated by a toy description with t = 0, which is not processed.
The required output is a line of the form “Toy #: ?
”, where #
denotes the toy sequence number starting at 1 and ?
is either Yes or No depending whether the toy can be properly built using at most 3 colors.
2 ( 20 10 21 2 20 ) 1 ( ( ( 10 1 10 0 ) ( 10 1 10 0 ) ) 10 1 10 ) 3 ( 32 31 20 21 10 0 10 30 20 ) 2 ( ( ( 10 1 10 21 1 21 10 ) ( 21 ) ) 0 10 20 ) 0 ( )
Toy 1: Yes Toy 2: Yes Toy 3: No Toy 4: Yes