![]() |
||||||||||||||||||||||||
Wojciech Rytter (treść, opracowanie) Piotr Sankowski (program wzorcowy) WirusyKomisja Badania Wirusów Binarnych wykryła, że pewne ciągi zer i jedynek są kodami wirusów. Komisja wyodrębniła zbiór wszystkich kodów wirusów. Ciąg zer i jedynek nazywamy bezpiecznym, gdy żaden jego segment (tj. ciąg kolejnych wyrazów) nie jest kodem wirusa. Komisja dąży do ustalenia, czy istnieje nieskończony, bezpieczny ciąg zer i jedynek. PrzykładDla zbioru kodów ZadanieNapisz program, który:
WejścieW pierwszym wierszu pliku wejściowego WIR.IN znajduje się jedna liczba całkowita n będąca liczbą wszystkich kodów wirusów. W każdym z kolejnych n wierszy znajduje się jedno niepuste słowo złożone ze znaków 0 i 1 - kod wirusa. Sumaryczna długość wszystkich słów nie przekracza 30000. WyjścieW pierwszym i jedynym wierszu pliku wyjściowego WIR.OUT powinno znajdować się słowo:
PrzykładDla pliku wejściowego WIR.IN3 01 11 00000poprawną odpowiedzią jest plik wyjściowy WIR.OUT NIE RozwiązanieAlgorytm teorio-grafowyW rozwiązaniu zadania najważniejszą rolę odgrywają sufiksy i prefiksy wirusów. Jeśli słowo Dla słowa ![]() Motywuje to wprowadzenie pomocniczego grafu G, którego ścieżki odpowiadają dokładnie wszystkim możliwym bezpiecznym słowom i którego węzłami są wszystkie bezpieczne prefiksy wirusów. Od węzła x prowadzimy skierowaną krawędź do y, gdy dla pewnej litery a (gdzie a=0 lub a=1) po dopisaniu jej do x otrzymamy słowo takie, że maksymalnym jego sufiksem, który jest prefiksem pewnego wirusa, jest y. Oznaczmy y przez
Rysunek 2 przedstawia graf G dla przykładowego zbioru wirusów ![]() Grafy tego typu odpowiadają w teorii obliczeń tzw. automatom skończonym. Zbiór W jest bezpieczny wtedy i tylko wtedy, gdy w grafie G istnieje cykl skierowany osiągalny z węzła startowego odpowiadającego słowu pustemu. Każda ścieżka w tym grafie zaczynająca się od węzła startowego wyznacza ciąg bezpieczny. Konstrukcja drzewa bezpiecznych prefiksów wirusówPierwszym krokiem w konstrukcji grafu G jest zbudowanie drzewa właściwych prefiksów wirusów, tzn. takich prefiksów słów ze zbioru W, które nie są równe żadnemu wirusowi. Drzewo dla przykładowego zbioru W jest przedstawione na rysunku 1. Uwaga: Załóżmy początkowo, że żaden wzorzec nie jest właściwym podsłowem innego wzorca.
Rys. 1. Początkowa "aproksymacja" grafu G: drzewo T bezpiecznych prefiksów wirusów. Linie przerywane oznaczają przejścia zabronione. Brakujące niezabronione przejścia są uzupełnione w grafie G. ![]() Wierzchołki są ponumerowane, jednakże każdy węzeł utożsamiamy z pewnym prefiksem wzorca. Załóżmy, że syn(x,a) oznacza węzeł xa, jeśli xa jest bezpiecznym prefiksem wzorca. Jeśli Właściwa konstrukcja grafu
Algorytm korzysta istotnie z drzewa prefiksów T zbudowanego wcześniej i opisanego funkcją syn. Algorytm Inicjujemy Przechodząc drzewo T wszerz, dla każdego węzła
Uwaga: Założenie, że żaden wirus nie jest podsłowem innego wirusa było użyteczne przy wprowadzeniu pomocniczego drzewa prefiksów. Algorytm konstrukcji grafu automatycznie wykrywa takie sytuacje, tak więc założenie to nie jest istotne.
Rys. 2. Graf G dla przykładowego zbioru wirusów. Pogrubione krawędzie (przejścia) są pozostałością z drzewa prefiksów T, pozostałe krawędzie powstały w wyniku działania algorytmu konstrukcji G. ![]() Sprawdzanie acyklicznościAby stwierdzić, czy w grafie jest cykl należy sprawdzić, czy wierzchołki grafu można posortować topologicznie. Można zastosować dwie alternatywne metody:
Nie opisujemy dokładnie tych metod ponieważ sprawdzanie acykliczności grafu wystąpiło już w wielu poprzednich zadaniach olimpijskich. Dla naszego przykładowego zbioru wirusów nieskończona ścieżka "idąca" po węzłach grafu G. ![]() odpowiada nieskończonemu bezpiecznemu słowu: ![]() Algorytm alternatywnyWprowadzamy dwie operacje na zbiorze W. Niech Usuwanie y. Jeśli x jest podsłowem y, to y usuwamy z W. Skracanie y. Jeśli y = za, gdzie Symbol Na przykład jeśli x = 0010, y = 001010011, to skracając y dostajemy y=00101001. Operację skracania możemy zastosować dlatego, że jeśli w pewnym nieskończonym ciągu wystąpi skrócone y, to albo w tym ciągu wystąpi samo y, albo x. Niech W' będzie zbiorem powstałym z W za pomocą jednej z tych operacji, wtedy: ![]() Łatwo zauważyć, że W jest niebezpieczny wtedy i tylko wtedy, gdy po pewnej liczbie operacji otrzymamy zbiór zawierający oba pojedyncze symbole jako słowa. Natomiast, jeśli w wyniku dowolnego ciągu operacji otrzymamy zbiór zawierający słowo o długości większej niż jeden, to W jest bezpieczny. Można wówczas skonstruować dowolnie długi bezpieczny ciąg postępując w następujący sposób: zaczynamy od ciągu pustego i dokładamy po jednym symbolu, do chwili gdy otrzymujemy ciąg niebezpieczny (gdy sufiks należy do w); zamieniamy ostatnio dodany symbol na przeciwny i kontynuujemy naszą konstrukcję. Nasz algorytm polega na stosowaniu w dowolnej kolejności jednej z powyższych operacji, aż otrzymany zbiór zawierający obie litery 0,1, albo zbiór zawierający dłuższe słowo, który to zbiór nie da się dalej zmienić za pomocą jednej z naszych operacji. W pierwszym przypadku W jest niebezpieczny. Dla naszego przykładowego zbioru wirusów W z rysunku 1 od razu widać, że jest on bezpieczny, ponieważ żadna z dwóch operacji się do niego nie stosuje. PrzykładRozważmy przykład zbioru, który nie jest bezpieczny. W poniższym ciągu przekształceń podkreślamy słowo biorące udział w przekształceniu, słowo to jest usuwane lub skracane o jeden symbol od końca. Zatem TestyDo sprawdzania rozwiązań zawodników użyto 10 testów: |