| III Mistrzostwa Wielkopolski w Programowaniu Zespołowym | 2-3 grudnia 2005 |
|
|
Pewnego dnia prof. Axel Thue, wybitny norweski matematyk, wybrał się do lasu. Wszedł do lasu ścieżką, a po chwili zauważył rozwidlenie - ścieżka rozchodziła się na dwie, a na rozwidleniu, przed domem, stał jakiś człowiek. Prof. Thue skręcił w jedną z nich, a za chwilę spotkało go to samo - rozwidlenie, na którym ścieżka rozchodziła się na dwie, a na rozdrożu człowiek. Wybrał losową i szedł dalej. Ale i tym razem to samo. I tak szedł i szedł i za każdym razem napotykał takie samo rozdroże z człowiekiem. Cóż... Prof. Thue nic sobie z tego nie robił, a po udanym w sumie spacerze wrócił do domu.
Następnego dnia po raz kolejny wybrał się do tego samego lasu. Przed wyjściem dowiedział się jednak, że ludzie, którzy mieszkają w lesie przy rozwidleniach dróg są dość specyficzni. Otóż część z nich mówi zawsze prawdę, a część z nich zawsze kłamie, niezależnie od tego, o co się ich zapyta. Spodobało się to prof. Thue. Poszukał w pamięci tego sprytnego pytania, którym można było rozpoznać, czy ktoś jest kłamcą, czy nie. Nie pamiętał jednak dokładnie, więc zapytał się pierwszego z napotkanych tak: „Czy idąc w lewo na najbliższym rozwidleniu spotkam kłamcę?”. Padła odpowiedź: „Tak, oczywiście”. Zadowolony prof. poszedł losowo wybraną ścieżką, nie zastanawiając się do końca, co to znaczy, a jedynie notując odpowiedź, rozkoszował się pięknem otaczającej go przyrody. Jednak następnej spotkanej osobie zadał to samo pytanie i znów usłyszał tą samą odpowiedź. Znów to zanotował i znów poszedł dalej. I tak jeszcze kilka razy, a odpowiedź za każdym razem była ta sama. Cóż... Prof. Thue ze swoimi notatkami, po udanym w sumie spacerze, wrócił do domu.
Następnego dnia sytuacja powtórzyła się. Przed wyjściem profesor tym razem dowiedział się, że na każdym rozwidleniu, idąc w jedną stronę spotka na następnym kłamcę, a idąc w drugą spotka osobę prawdomówną. Prof. Thue podczas spaceru znów zadawał to samo pytanie i znów słyszał wciąż tę samą odpowiedź. Tym razem łono przyrody nie zapewniło mu aż takiej beztroski intelektualnej i zainteresował się tym. Po powrocie do domu wybrał się znowu do lasu, a potem przechodząc przez niego wiele razy do późnego wieczora praktycznie wszystkimi możliwymi ścieżkami i wciąż zadając to samo pytanie, wciąż uzyskiwał tę samą odpowiedź.
Następnego dnia stwierdził, że pytanie, które zadawał jest bez sensu i rzeczywiście nie mogło mu dać żadnej informacji o tym, czy ktoś kłamcą jest, czy też nie. Przygotował więc inne pytanie i chciał się wybrać do lasu. Niestety po całym poprzednim dniu biegania po lesie, biedak przeziębił się i gorączka uniemożliwiła mu spacer. Ale wtedy odwiedził chorego jego serdeczny przyjaciel, który powiedział z tryumfem, że rozgryzł człowieka stojącego na pierwszym rozwidleniu w lesie - wiadomo, że jest on kłamcą. W tym momencie prof. Thue, pomimo wysokiej gorączki, w jednej chwili domyślił się, kim jest każdy z mieszkańców lasu - czy człowiekiem prawdomównym, czy też kłamcą. Tzn. odkrył jedynie zasadę, dzięki której można stwierdzić, czy ktoś jest kłamcą, czy też nie.
Ponieważ las jest bardzo duży, ręczne dochodzenie do tego, czy ktoś jest kłamcą może trwać bardzo długo. Prof. Thue zapragnął mieć więc program, który rozstrzygnie za niego, czy ktoś jest kłamcą, czy nie. No i oczywiście zlecił to zadanie właśnie Tobie. Niestety gorączka znowu mu mocno skoczyła i nie był w stanie opowiedzieć Ci dokładnie, jak wygląda jego pomysł na rozstrzyganie tego. Ale nie chcesz chyba zrobić przykrości biednemu, schorowanemu profesorowi, więc na pewno uda Ci się samemu wymyślić sposób na stwierdzenie tego, kto jest kłamcą, a kto nie. A gotowy program podarujesz prof. Axelowi Thue na zbliżające się jego imieniny.
Pierwsza linia wejścia zawiera liczbę całkowitą D (1 ≤ D ≤ 50), oznaczającą liczbę zestawów danych, Jedyną linią zestawu danych jest liczba X (1 ≤ X ≤ 2000000000), oznaczającą, na którym rozwidleniu znajduje się człowiek, którego prawdomówność badamy. Jak widać, ścieżki w lesie tworzą drzewo binarne, a wierzchołki będziemy numerować tak, że korzeń (czyli pierwsze rozwidlenie w lesie) dostaje numer 1, jego dwaj synowie (czyli rozwidlenia, do których prowadzą drogi na które rozchodzi się droga wchodząca do lasu) numery 2 (prawo) i 3 ( lewo), synowie 2 numery 4 (prawo) i 5 (lewo), synowie 3 analogicznie numery 6 i 7, synowie 4 numery 8 i 9 itd... (obrazuje to też rysunek poniżej)
Dla każdego badanego człowieka należy na wyjściu w nowej linii wypisać cyfrę 1, jeśli jest to osoba prawdomówna, bądź 0, jeśli osoba jest kłamcą.
2 2 3
0 1