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
problem z liskami i owieczkami
-
Dasio11
- Moderator
- Posty: 10225
- Rejestracja: 21 kwie 2009, o 19:04
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 40 razy
- Pomógł: 2362 razy
Re: problem z liskami i owieczkami
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)}\).
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)}\).