problem z liskami i owieczkami

Zdania. Tautologie. Język matematyki. Wszelkie zagadnienia związane z logiką matematyczną...
Inicjatus
Użytkownik
Użytkownik
Posty: 1
Rejestracja: 26 kwie 2019, o 12:42
Płeć: Mężczyzna
Lokalizacja: Bialystok

problem z liskami i owieczkami

Post autor: Inicjatus » 26 kwie 2019, o 13:33

Siedze nad tym zadaniem juz kilka dni i nie wpadlem na jakis dobry pomysl. Zadanie niby jest z informatyki jednak nie radze sobie z problem matematyczny dlatego wybralem to forum. Bylbym bardzo wdzieczny za jakies podpowiedzi oto tresc:

Przemek poszedł do zoo. Jest tam \(\displaystyle{ n}\) zwierząt ustawionych w okrąg. Każde z tych zwierząt jest jednego z dwóch
gatunków: szczere owce, które zawsze mówią prawdę i liski kłamczuszki, które zawsze kłamią.
Przemek nie rozróżnia, które zwierzęta jakiego są gatunku, więc aby się tego dowiedzieć, zadał każdemu
następujące pytanie: czy twoi sąsiedzi (na okręgu) są tego samego gatunku? Dokładniej, czy gatunek zwierzęcia
bezpośrednio po lewej stronie jest taki sam jak gatunek zwierzęcia bezpośrednio po prawej stronie? Każde zwierzę odpowiedziało na pytanie “tak” lub “nie”.
Twoim zadaniem jest stwierdzić, czy istnieje takie przypisanie gatunków do zwierząt, które jest spójne z ich odpowiedziami.

\(\displaystyle{ Wejscoe}\)
W pierwszym i jedynym wierszu wejścia znajduje się słowo złożone z n znaków \(\displaystyle{ \left( 3 \le n \le 10^{6} \right)}\), i-ty znak jestrówny \(\displaystyle{ 1}\), jeśli i-te zwierzę odpowiedziało “tak”, a w przeciwnym wypadku jest równe \(\displaystyle{ 0}\).

\(\displaystyle{ Wyjscie}\)
Na wyjściu należy wypisać \(\displaystyle{ TAK}\), jeśli istnieje niesprzeczne przypisanie gatunków, \(\displaystyle{ NIE}\) w przeciwnym przypadku.

\(\displaystyle{ Przyklad}\)

\(\displaystyle{ 110110}\)

\(\displaystyle{ TAK}\)

\(\displaystyle{ Przyklad 2}\)

\(\displaystyle{ 110}\)

\(\displaystyle{ NIE}\)

A i wiem ze mozna sprawdzac wszystkie \(\displaystyle{ 2^{n}}\) opcji jednak mnie jak i sprawdzarke to nie satysfakcjonuje i wolalbym jakis bardziej finezyjny sposob

Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 8518
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 36 razy
Pomógł: 1780 razy

Re: problem z liskami i owieczkami

Post autor: Dasio11 » 27 kwie 2019, o 11:08

Niech \(\displaystyle{ x_1, \ldots, x_n}\) będzie takim ciągiem zer i jedynek, że \(\displaystyle{ x_i = 0}\) jeśli \(\displaystyle{ i}\)-te zwierzę jest lisem i \(\displaystyle{ x_i = 1}\) jeśli \(\displaystyle{ i}\)-te zwierzę jest owcą. Ponadto dla uproszczenia zapisu rozumowania przyjmijmy, że \(\displaystyle{ x_0 = x_n, x_{n+1} = x_1,}\) itd. Oznaczmy też \(\displaystyle{ i}\)-ty bit wejścia - czyli odpowiedź na pytanie zadane \(\displaystyle{ i}\)-temu zwierzęciu - przez \(\displaystyle{ w_i}\).

Niech \(\displaystyle{ \oplus}\) oznacza operację \(\displaystyle{ \mathrm{xor}}\). Nietrudno sprawdzić, że wtedy \(\displaystyle{ w_i = x_{i-1} \oplus x_i \oplus x_{i+1}}\). W związku z tym odpowiedź dla wejścia \(\displaystyle{ w_1 w_2 \ldots w_n}\) powinna brzmieć "tak" wtedy i tylko wtedy, gdy poniższy układ o zmiennych \(\displaystyle{ x_1, \ldots, x_n}\) i parametrach \(\displaystyle{ w_i}\):

\(\displaystyle{ $ \setlength\arraycolsep{0pt} $ \left\{ \begin{array}{l >{{}}c<{{}} l >{{}}c<{{}} l >{{}}c<{{}} l >{{}}c<{{}} l >{{}}c<{{}} l @{{}={}} l} x_1 & \oplus & x_2 & & & & & & & \oplus & x_n & w_1 \\ x_1 & \oplus & x_2 & \oplus & x_3 & & & & & & & w_2 \\ & & x_2 & \oplus & x_3 & \oplus & x_4 & & & & & w_3 \\ & & & & & & \ddots \\ & & & & & & x_{n-2} & \oplus & x_{n-1} & \oplus & x_n & w_{n-1} \\ x_1 & & & & & & & \oplus & x_{n-1} & \oplus & x_n & w_n \end{array} \right.}\)

ma rozwiązanie w \(\displaystyle{ \{ 0, 1 \}}\).

Hint: tego układu nie trzeba rozwiązywać eliminacją Gaussa, co dałoby niezbyt dobry czas \(\displaystyle{ \mathcal{O}(n^3)}\).

ODPOWIEDZ