eolymp
bolt
Try our new interface for solving problems

Colors

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 \textit{active} or \textit{inactive}. At any moment there is exactly one \textit{active component} per each \textit{module} and \textit{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 \textit{three colors} and \textit{adjacent components}must have \textit{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: 1. \textbf{<toy> ::= <last-track><module>} The current \textbf{<toy>} consists of a main \textbf{<module>}. \textbf{<last-track>} gives the number of the last track used to build the current \textbf{<toy>}; the tracks are numbered from \textbf{0} to \textbf{<last-track>}. 2. \textbf{<module> ::= '(' <operator-sequence> ')'} \textbf{<module>} represents a simple module that only contains operators. The operators given by the \textbf{<operator-sequence>} are processed in a left-to-right order. This \textbf{<module>} starts with empty tracks and then automatically adds one active component on each of the available tracks. 3. \textbf{<merged-module> ::= '(' <module>_1<module>_2 ')'} This is a merge operation that builds a complex \textbf{<merged-module>} by merging the active components of\textbf{<module>_1} and \textbf{<module>_2}, after both modules are completely built. 4. \textbf{<module> ::= '(' <merged-module><operator-sequence> ')'} The components of the \textbf{<merged-module>} remain on the tracks and its active components are further worked upon by the operators given by \textbf{<operator-sequence>}. 5. \textbf{<operator-sequence> ::= λ | <operator><operator-sequence>} 6. \textbf{<operator> ::= <node-operator> | <edge-operator>} 7. \textbf{<node-operator> ::= <track-number>} A \textbf{<node-operator>} adds an active component on the specified \textbf{<track-number>} for the current module and the previously active component on that track becomes inactive. 8. \textbf{<edge-operator> ::= <track-number-pair>} An \textbf{<edge-operator>} links the active components of the two track-numbers. 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. \textbf{Example 1} \textit{\textbf{Figure 1}} depicts a \textbf{3}-colorable toy that can be built using the following blueprint: \textbf{2 ( 20 10 21 2 20 )} \includegraphics{https://static.e-olymp.com/content/67/67885274d1a77fb54bcf873fa2261c7f3a952af9.jpg} \textit{\textbf{Figure 1}}: \textbf{3}-colorable toy There are \textbf{3} tracks numbered \textbf{0}, \textbf{1}, \textbf{2}. The toy consists of a single module containing \textbf{4} components labeled \textbf{a}, \textbf{b}, \textbf{c},\textbf{d}, linked by the lines \textbf{c--a}, \textbf{b--a}, \textbf{c--b}, \textbf{d--a}. To build this toy the robot will execute in order the following operations: \begin{enumerate} \item Add \textbf{a} on track \textbf{0}, \textbf{b} on track \textbf{1}, \textbf{c} on track \textbf{2}. At this stage \textbf{a}, \textbf{b} and \textbf{c} are the active components. \item Make the links \textbf{c--a}, \textbf{b--a} and \textbf{c--b}. \item Add \textbf{d} on track \textbf{2}, which makes \textbf{d} active and inactivates \textbf{c}. \item Make the link \textbf{d--a}. At this stage \textbf{a}, \textbf{b} and \textbf{d} are the active components. \end{enumerate} Note that the same toy can also be built using several other blueprints, such as the following two: \textbf{2 ( 10 20 21 2 20 )} \textbf{2 ( ( ( 20 10 ) ( 21 ) ) 2 20 )} \textbf{Example 2} \textit{\textbf{Figures 2}} and \textit{\textbf{3}} illustrate a sequence of operations involving a merge, for another \textbf{3}-colorable (in fact even \textbf{2}-colorable) toy that can be built as specified by the following blueprint: \textbf{1 ( ( ( 10 1 10 0 ) ( 10 1 10 0 ) ) 10 1 10 )} 1. First, module \textbf{1} is built: (a) Add a on track \textbf{0} and \textbf{b} on track \textbf{1}. (b) Link \textbf{b--a}. (c) Add \textbf{c} on track \textbf{1}. (d) Link \textbf{c--a}. (e) Add \textbf{d} on track \textbf{0}. \textbf{c} and \textbf{d} are now the active components of module \textbf{1}. 2. Secondly, module \textbf{2} is built using similar operations. \textbf{g} and \textbf{h} are now the active components of module \textbf{2}. 3. Thirdly, modules \textbf{1} and \textbf{2} are merged together, which means that active components of each track are identified, i.e., \textbf{c = g} and \textbf{d = h}. The snapshot of \textit{\textbf{Figure 2}} illustrates this moment, with braces showing component identification. \textbf{(c + g)} and \textbf{(d + h)} are now the active components of the merged module \textbf{1 + 2}. 4. Fourthly, the just merged components are linked, i.e., \textbf{(c + g)--(d + h)}. 5. Lastly, \textbf{i} is added to track \textbf{1} and linked with \textbf{(d+h)}. The final result is depicted in \textit{\textbf{Figure 3}} and links made after the merging are depicted with double lines. At the end, \textbf{i} and \textbf{(d+h)} are the active components of the main module. \InputFile The input will consist of a sequence of toy blueprints, one per line of at most \textbf{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 \textbf{t}, \textbf{0} ≤ \textbf{t} ≤ \textbf{6}, denoting the maximum track number for the robot’s arms to grab (i.e., there are \textbf{t + 1} current components for the robot). The interpretations for the remaining tokens are given in the next table. The input will be terminated by a toy description with \textbf{t = 0}, which is not processed. \OutputFile The required output is a line of the form "\textbf{Toy #: ?}", where \textbf{#} denotes the toy sequence number starting at \textbf{1} and \textbf{?}is either \textbf{Yes} or \textbf{No} depending whether the toy can be properly built using at most \textbf{3} colors.
Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri #1
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 ( )
Çıxış verilənləri #1
Toy 1: Yes
Toy 2: Yes
Toy 3: No
Toy 4: Yes
Mənbə ACM International Collegiate Programming Contest, Summer Camp (2nd Day), Tokyo, 2005–9–24