Runda 16 [Hard] - Spacer po kostce

21.03.2011 - Damian Rusak
TrudnośćTrudność

 

Zadanie tygodnia

runda 16; kategoria Hard

Limit czasowy: 1s; Limit pamięciowy: 32MB


Spacer po kostce

Wiemy dobrze czym są odcinek, kwadrat albo sześcian. Jak jednak wyglądałaby analogiczna figura w $ n $ wymiarach?

W $ n $ wymiarowej przestrzeni żyje sobie robaczek Adam. Ciężko jest sobie wyobrazić $ n $- wymiarową przestrzeń, zatem Adam wpadł na pomysł, jak opowiadać znajomym z niższych wymiarów o swoim świecie. Adam mieszka w hiperkostce - możemy myśleć o takim obiekcie jak o grafie, który ma $ 2^{n} $ wierzchołków (dla przestrzeni jednowymiarowej jest to odcinek, dla dwuwymiarowej kwadrat, dla trójwymiarowej sześcian itd.) numerowanych liczbami od $ 0 $ do $ 2^{n}-1 $. Dwa wierzchołki takiego grafu są połączone krawędzią nieskierowaną, jeśli ich numery zapisane w systemie binarnym różnią się dokładnie na jednej pozycji.  (na przykład dla $ n = 2 $ można ponumerować wierzchołki kwadratu liczbami od $ 0 $ do $ 3 $ - wtedy połączone są pary  wierzchołków $ (0,1) $, $ (0,2) $, $ (1,3) $, $ (2,3) $, gdyż ich zapisy binarne to $ (00,01) $, $ (00,10) $, $ (01,11) $, $ (10,11) $)

Adam uwielbia podróżować po hiperkostce i pragnie opowiedzieć nam, jak wygląda jego podróż. Chciałby wystartować w wierzchołku o numerze $ x $ i przejść po wszystkich wierzchołkach hiperkostki, tak, aby w każdym z nich być dokładnie jeden raz. Oczywiście podróż taka może przebiegać jedynie po krawędziach łączących wierzchołki. Jednak ma problem z opisaniem takiej podróży i poprosił Cię o pomoc.

Wejście:

Jedyna linia wejścia zawiera dwie liczby $ n $ oraz $ x $ - odpowiednio wymiar przestrzeni w której wędruje Adam, oraz numer wierzchołka z którego pragnie rozpocząć podróż. ($ 1 \leq n \leq 18, 0 \leq x \leq 2^{n}-1 $).

Wyjście:

Wyjście powinno składać się z jednej linii, zawierającej $ 2^{n} $ liczb - numerów kolejnych wierzchołków (poczynając od $ x $) po których kroczył będzie Adam, tak, że każde dwa kolejne numery odpowiadają wierzchołkom połączonym krawędzią i każdy numer ze zbioru $ {0,...,2^{n}-1} $ występuje dokładnie raz. Jeśli możliwe jest wiele odpowiedzi, Twój program może wypisać dowolną z nich.

Przykład:

Wejście:

2 1

Wyjście:

1 0 2 3

 

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
PozycjaImię i nazwiskoWynikCzasSpacer po kostce
1Kamil Dębowski1000:45:5110
2Wojtek Nadara1001:29:4110
3Damian Straszak1002:11:4410
4Przemysław Derengowski1003:49:3610
5Piotr Bejda1005:39:3810
6Paweł Szczur1029:17:2010
7Krzysztof Pszeniczny1034:15:1010
8Wojciech Szałapski1038:02:0010
9Adam Tażyk1038:08:4010
10Witold Długosz1055:41:3810
11Krzysztof Drab1059:35:5710
12Eric Bana10103:05:1210
13Mateusz Wasylkiewicz10109:32:0110
14Bartłomiej Gajewski10130:44:0310
15Bartek Dudek10151:07:0310
16Paweł Kura10156:34:2810
17Krzysztof Cirocki2153:55:192
18Michal Filipczak2191:16:352
4.5
Twoja ocena: Brak Ocena: 4.5 (2 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com