IV Olimpiada Informatyczna 1996/1997
|
Task: GEN
|
Author: Przemysława Kanarek
|
II stage contest |
Source file | GEN.??? (e.g. PAS,C, CPP) |
Executable file | GEN.EXE |
Input file | GEN.IN |
Output file | GEN.OUT |
Genotype is a finite sequence of genes. It can be described by words built of capital letters A-Z of the English alphabet. Different letters denote different kinds of genes. A gene can bud and in effect transform into a pair of new genes. Such transformations are controlled by a finite set of rules. Every rule of budding can be described by three capital letters A1A2A3. Such a description means that gene A1 can transform into the pair of genes A2A3.
We are using S to denote the special kind of genes called supergenes. The breeding of a genotype begins from a sequence of supergenes and it consists in controlled budding of chosen genes according to the given rules.
In the next line there is written one integer k, 1 <= k <= 10000. In each of the following k lines there is one genotype. Such a genotype is described by a non-empty word consisting of at most 100 letters A - Z.
6 SAB SBC SAA ACA BCC CBC 3 ABBCAAABCA CCC BAthe correct solution is file GEN.OUT:
3 1 NIE