W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Każda bramka XOR ma dwa wejścia i jedno wyjście, a jej działanie opisuje następująca tabelka:
wejście 1 wejście 2 wyjście 0 0 0 0 1 1 1 0 1 1 1 0
Siecią XOR nazywamy układ bramek XOR, mający wejść i jedno wyjście, spełniający następujące warunki:
Przedstawiony na rysunku układ bramek mający wejść i 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 do . Stan wejść sieci XOR opisuje słowo wejściowe utworzone z cyfr dwójkowych i — przyjmujemy, że -ta od lewej cyfra danego słowa wejściowego, to stan -tego wejścia sieci. Dla dowolnego stanu wejść sieć daje na wyjściu albo . 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.
Napisz program, który:
Zakładamy, że: , oraz, że bramki danej sieci są ponumerowane w dowolnym porządku liczbami od do .
W pierwszym wierszu standardowego wejścia są zapisane trzy liczby całkowite dodatnie pooddzielane pojedynczym odstępem. Jest to liczba wejść danej sieci XOR, liczba bramek oraz numer bramki połączonej z wyjściem sieci.
W kolejnych wierszach znajdują się opisy połączeń bramek sieci. W -tym z tych wierszy, dla od do , znajduje się opis połączeń dwóch wejść bramki o numerze , który ma postać dwóch liczb całkowitych nie mniejszych niż i nie większych niż , oddzielonych pojedynczym odstępem. Jeśli odpowiednie wejście do bramki jest połączone z wejściem do sieci o numerze , to opisem tego połączenia jest liczba ujemna , a jeśli wejście do bramki jest połączone z wyjściem innej bramki o numerze , to opisem tego połączenia jest liczba dodatnia .
W kolejnych dwóch wierszach są zapisane dwa -bitowe słowa oraz . Jest to dolne i górne ograniczenie zakresu testowania sieci. Zakładamy, że w danym zakresie mieści się nie więcej niż słów.
Na standardowe wyjście 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 z danego zakresu: , gdzie nierówność należy rozumieć jako relację porządku zgodnego z wartościami liczbowymi słów dwójkowych.
Dla danych wejściowych:
5 6 5 -1 -2 1 3 1 -2 2 -3 4 6 -4 -5 00111 01110
poprawną odpowiedzią jest:
5
Autor zadania: Tomasz Śmigielski.