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.