Układy asemblerowe

Limit pamięci: 32 MB

Firma Bajtel postanowiła usprawnić produkowane przez nią komputery, przez zastąpienie zaszytych w komputerach programów asemblerowych specjalnymi układami elektronicznymi, zwanymi układami asemblerowymi. Programy asemblerowe składają się wyłącznie z przypisań. Każde przypisanie jest określone przez cztery elementy:

• dwa rejestry, z których pobierane są dane,
• operację elementarną, wykonywaną na tych danych,
• rejestr, w którym umieszczany jest wynik.

Zakładamy, że jest co najwyżej rejestrów oznaczonych małymi literami alfabetu angielskiego od a do z oraz co najwyżej różne operacje elementarne oznaczone wielkimi literami angielskiego alfabetu od A do D.

Układ asemblerowy ma:

• wejścia oznaczone nazwami rejestrów, na każde wejście podawana jest wartość początkowa odpowiedniego rejestru, oraz
• wyjścia oznaczone również nazwami rejestrów, których wartości końcowe są kierowane do tych rejestrów.

Wewnątrz układu znajdują się bramki. Każda bramka ma dwa wejścia i jedno wyjście. Wykonuje ona jedną operację elementarną na danych, które pojawiają się na jej wejściach i udostępnia wynik na swoim wyjściu. Wejścia bramek oraz wyjścia całego układu są połączone z wyjściami innych bramek lub wejściami układu. Wyjścia bramek oraz wejścia układu mogą być połączone z wieloma wejściami innych bramek lub wyjściami układu. Połączenia między bramkami nie tworzą cykli.

Układ asemblerowy jest równoważny programowi asemblerowemu, gdy dla dowolnego stanu początkowego rejestrów daje taki sam — jak program — stan końcowy rejestrów.

Zadanie

Napisz program, który:

• wczytuje ze standardowego wejścia opis programu asemblerowego;
• oblicza najmniejszą liczbę bramek, które musi zawierać układ asemblerowy równoważny z danym programem;
• zapisuje wynik na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita (). Jest to liczba instrukcji programu.

W kolejnych wierszach opisane są kolejne instrukcje programu. Każdy opis ma postać czteroliterowego słowa, zaczynającego się od symbolu operacji elementarnej: A, B, C albo D. Pozostałe trzy litery są małe. Druga i trzecia — to nazwy rejestrów, z których należy pobrać dane; czwarta — to nazwa rejestru, w którym należy umieścić wynik.

Wyjście

Twój program powinien zapisać w pierwszym i jedynym wierszu standardowego wyjścia jedną liczbę całkowitą — minimalną liczbę bramek układu asemblerowego, równoważnego danemu programowi.

Przykład

Dla danych wejściowych:

8
Afbc
Bfbd
Cddd
Bcbc
Afcc
Afbf
Cfbb
Dfdb

poprawną odpowiedzią jest:

6

Układ równoważny danemu programowi przedstawiono na rysunku.

Autor zadania: Marcin Kubica.