Genotypy
Limit pamięci: 32 MB
Genotypy są skończonymi łańcuchami genów.
Opisujemy je za pomocą słów utworzonych z wielkich liter alfabetu angielskiego A–Z.
Różne litery oznaczają różne rodzaje genów.
Gen może pączkować — zmieniając się w dwójkę nowych genów.
Tymi przemianami rządzi skończony zbiór reguł.
Każdą regułę pączkowania można zapisać w postaci trójki wielkich liter co oznacza,
że gen może się zmienić w dwójkę genów .
Wielką literą oznaczamy specjalny rodzaj genów zwanych supergenami.
Hodowla genotypu rozpoczyna się od łańcucha supergenów i polega na sterowanym pączkowaniu wybranych genów zgodnie z ustalonymi regułami.
Zadanie
Napisz program, który:
- wczytuje ze standardowego wejścia skończony zbiór reguł pączkowania genów oraz ciąg słów określających genotypy, jakie należy wyhodować,
- dla każdego z danych genotypów bada, czy można go wyhodować z pewnego skończonego łańcucha supergenów zgodnie z danymi regułami pączkowania
i jeśli tak, znajduje minimalną długość takiego łańcucha,
- zapisuje wyniki na standardowe wyjście.
Wejście
W pierwszym wierszu standardowego wejścia jest zapisana jedna liczba całkowita , .
W każdym z kolejnych wierszy jest zapisana jedna reguła pączkowania,
w postaci słowa złożonego z trzech wielkich liter A–Z.
Dopuszczalne są reguły pączkowania, w których na drugim lub trzecim miejscu występuje supergen.
W następnym wierszu jest zapisana jedna liczba całkowita , .
W każdym z kolejnych wierszy jest zapisany jeden genotyp w postaci niepustego słowa złożonego z co najwyżej liter A–Z.
Wyjście
W -tym z kolejnych wierszy standardowego wyjścia należy zapisać:
- jedną liczbę całkowitą dodatnią oznaczającą minimalną długość łańcucha supergenów potrzebnego do wyhodowania -tego danego genotypu, albo
- jedno słowo NIE, jeśli tego genotypu nie da się wyhodować.
Przykład
Dla danych wejściowych:
6
SAB
SBC
SAA
ACA
BCC
CBC
3
ABBCAAABCA
CCC
BA
poprawną odpowiedzią jest:
3
1
NIE
Autor zadania: Przemysława Kanarek.