1378 . History of Dots
Description
Dots are peculiar two dimensional creatures. Since the creation of the dot universe, each dot
resides in a unique and isolated community, all interactions and communications between dots are
limited to the dots in the same community; also, the number of dots never changes, i.e., no birth nor
death will ever occur for dots. Dots come in assorted colors, when two dots of different colors meet
they would transform to another pair of colors according to the transformation rules in the book of
life. More often than not, a dot community would reach the eternal state and never transform again,
such as, when all dots in a community are settled in one identical color, then no more transformations
could ever happen again. It is still a mystery how the dots come into being (rumor has it that they
are created during an ACM programming contest). As the dots stay in the eternal state, they have
endless time to speculate their origin. Since it is very difficult to study the moment of creation, they
decide to first study the probable initial population states, that is the number of dots in each color at
the beginning. Even this is not an easy task, first of all they have to find out the color transformation
rules, and secondly they have to find out as much as possible about the past so that they can rule out
any impossible initial population. Luckily, they do manage to find out certain historical facts of their
communities in the form of a sequence of transient population states, so that they know that some
specific population states appeared in a specific order in time. Your mission is to write a program,
given the number of dots, the number of colors, the color in the eternal state, the color transformation
rules, a set of initial populations, and perhaps a series of past transient population states, to determine
which initial population is possible and which is not.
Let n (1 ≤ n ≤ 30) be the number of dots, k (1 ≤ k ≤ 5) be the number of colors, and
C = {1, 2,..., k} be the set of colors. Each color transformation rule is presented in the form of
ci cj ci' cj' , which means that when a dot in color ci and a dot in color cj meet (i ≠ j), they transform
to dots in color ci' and cj' . There is no transformation when two dots of the same color meet. Only rules result in a transformation are listed in the book of life. The color for the final eternal state will
be ce ∈ C. The initial population and each of the transient population states (at most 5) are presented
by (n1 , n2 ,..., nk ) where nj (1 ≤ j ≤ k) is the number of dots in color j and
Input Format
The input file is a text file with two test cases. Each test case comprises two text lines, with the first
line listing the number of dots (n), the number of colors (k), the color of dots in the eternal state (ce ), a series of transient population states (at most 5), and the transformation rules. The second line is a
series of possible initial population states (at most 10 per test case).
Output Format
For each test case, output a sequence of 0 and 1 in one line, where 0 indicates that corresponding initial
population is not possible, and 1 means possible.
Sample Input 1
4 2 2 (2,2) 1 2 2 2 (4,0)(2,2)(0,4) 6 3 3 (2,3,1) 1 2 2 2 2 3 3 3 (4,2,0)(3,2,1)(2,2,2)(1,4,1)
Sample Output 1
0 1 0 0 1 0 0
Hints
Problem Source
Migrated from old NTUJ.
The ACM-ICPC 2010 Asia Regional Contest, Site Kaohsiung
Subtasks
| No. | Testdata Range | Score |
|---|