V Olimpiada Informatyczna 1997/98
|
Zadanie: UKL
|
Autor: Marcin Kubica
|
III Etap, SESJA PRÓBNA - PONIEDZIAŁEK 6 KWIETNIA 1998 r. |
Plik źródłowy: | UKL.??? (np. pas, c, cpp) |
Plik wykonywalny: | UKL.exe |
Plik wejściowy: | UKL.in |
Plik wyjściowy: | UKL.out |
Firma Bajtel postanowiła usprawnić produkowane przez
nią komputery, przez zastąpienie zaszytych w
komputerach programów assemblerowych specjalnymi
układami elektronicznymi, zwanymi układami
assemblerowymi. Programy assemblerowe składają się
wyłącznie z przypisań. Każde przypisanie jest określone
przez cztery elementy:
Zakładamy, że jest co najwyżej 26 rejestrów
oznaczonych małymi literami alfabetu angielskiego
od a do z oraz co najwyżej 4 różne operacje
elementarne oznaczone wielkimi literami angielskiego
alfabetu od A do D.
Układ assemblerowy ma:
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 assemblerowy jest równoważny programowi assemblerowemu, gdy dla dowolnego stanu początkowego rejestrów daje taki sam - jak program -stan końcowy rejestrów.
ZadanieNapisz program, który:
W pierwszym wierszu pliku wejściowego UKL.IN znajduje się jedna liczba całkowita n (1 <= n < 1000). Jest to liczba instrukcji programu.
W n 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.
Twój program powinien zapisać w pierwszym i jedynym wierszu pliku wyjściowego UKL.OUT jedną liczbę całkowitą - minimalną liczbę bramek układu assemblerowego, równoważnego danemu programowi.
Dla pliku tekstowego UKL.IN:
8 Afbc Bfbd Cddd Bcbc Afcc Afbf Cfbb Dfdb
poprawnym rozwiązaniem jest plik wyjściowy UKL.OUT:
6
Układ równoważny danemu programowi przedstawiono na rysunku.