szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna
PostNapisane: 26 kwi 2019, o 13:33 
Użytkownik

Posty: 1
Lokalizacja: Bialystok
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 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.

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

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

Przyklad

110110

TAK

Przyklad 2

110

NIE

A i wiem ze mozna sprawdzac wszystkie 2^{n} opcji jednak mnie jak i sprawdzarke to nie satysfakcjonuje i wolalbym jakis bardziej finezyjny sposob
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2019
Góra
Mężczyzna
PostNapisane: 27 kwi 2019, o 11:08 
Moderator
Avatar użytkownika

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

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

$ \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 \{ 0, 1 \}.

Hint: tego układu nie trzeba rozwiązywać eliminacją Gaussa, co dałoby niezbyt dobry czas \mathcal{O}(n^3).
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Problem z dowodzeniem formuł  pajq  5
 Problem ze zrozumieniem zadania  Grrrr  7
 maly problem  rafixp  1
 Problem z prawem rachunku kwantyfikatorów  Leop  1
 Problem nierozstrzygalności  martaol  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl