|
||||||||||||||||||||||||||||||
|
Bramki XOR
Każda bramka XOR ma dwa wejścia i jedno wyjście, a jej działanie opisuje następująca tabelka
Siecią XOR nazywamy układ bramek XOR, mający n wejść i jedno wyjście, spełniający następujące warunki:
PrzykładPrzedstawiony na rysunku układ 6 bramek mający 5 wejść i 1 wyjście spełnia warunki 1 - 5, więc jest siecią XOR. Uwaga: bramki na rysunku zostały ponumerowane dowolnie, ale istnieje numeracja spełniająca warunek określony w punkcie 5. Wszystkie wejścia sieci są ponumerowane od 1 do n. Stan wejść sieci XOR opisuje słowo wejściowe utworzone z n cyfr dwójkowych 0 i 1 - przyjmujemy, że i-ta od lewej cyfra danego słowa wejściowego, to stan i-tego wejścia sieci. Dla dowolnego stanu wejść sieć daje na wyjściu 0 albo 1. Każde słowo wejściowe jest dwójkowym zapisem jakiejś liczby naturalnej, więc słowa te można uporządkować zgodnie z ich wartościami liczbowymi. Sieci XOR będziemy testowali podając na wejściu kolejne słowa z ustalonego zakresu i zliczając liczbę otrzymanych w wyniku jedynek. ZadanieNapisz program, który:
WejścieW pierwszym wierszu pliku tekstowego XOR.IN są zapisane trzy liczby całkowite dodatnie pooddzielane pojedynczym odstępem. Jest to liczba wejść n danej sieci XOR, liczba bramek m oraz numer bramki połączonej z wyjściem sieci. W kolejnych m wierszach znajdują się opisy połączeń bramek sieci. W i-tym z tych wierszy, dla i od 1 do m, znajduje się opis połączeń dwóch wejść bramki o numerze i, który ma postać dwóch liczb całkowitych nie mniejszych niż -n i nie większych niż m, oddzielonych pojedynczym odstępem. Jeśli odpowiednie wejście do bramki jest połączone z wejściem do sieci o numerze k, to opisem tego połączenia jest liczba ujemna -k, a jeśli wejście do bramki jest połączone z wyjściem innej bramki o numerze j, to opisem tego połączenia jest liczba dodatnia j. W kolejnych 2 wierszach pliku tekstowego XOR.IN są zapisane dwa n-bitowe słowa a oraz b. Jest to dolne i górne ograniczenie zakresu testowania sieci. Zakładamy, że w danym zakresie mieści się nie więcej niż sto tysięcy słów. WyjścieW pliku tekstowym XOR.OUT należy zapisać jedną liczbę całkowitą nieujemną - liczbę jedynek, jakie powinniśmy otrzymać na wyjściu poprawnie działającej danej sieci XOR dla słów wejściowych s z danego zakresu: a Ł s Ł b, gdzie nierówność Ł należy rozumieć jako relację porządku zgodnego z wartościami liczbowymi słów dwójkowych. PrzykładDla pliku XOR.IN, zawierającego opis przedstawionej powyżej sieci XOR: 5 6 5 -1 -2 1 3 1 -2 2 -3 4 6 -4 -5 00111 01110poprawnym rozwiązaniem jest następujący plik XOR.OUT: 5 Twój program powinien szukać pliku XOR.IN w katalogu bieżącym i tworzyć plik XOR.OUT również w bieżącym katalogu. Plik zawierający napisany przez Ciebie program w postaci źródłowej powinien mieć nazwę XOR.???, gdzie zamiast ??? należy wpisać co najwyżej trzyliterowy skrót nazwy użytego języka programowania. Ten sam program w postaci wykonalnej powinien być zapisany w pliku XOR.EXE |