Runda 13 [Hard] - Wężoślad

28.02.2011 - Damian Rusak
TrudnośćTrudność

 

Zadanie tygodnia

runda 13; kategoria Hard

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


Wężoślad

Grupa badaczy wyruszyła do tajemniczej, pierwotnej dżungli, aby poznać zwyczaje żyjących tam stworzeń. Jednym z najbardziej fascynujących okazów jest Wąż Kątoprosty - jedyny znany nauce gatunek węża, który w czasie poruszania się zgina swe ciało jedynie pod kątami, które są wielokrotnością kąta prostego. 

Badaczom udało się przyjrzeć jego zachowaniom godowym - każdemu wężowi można przypisać liczbę całkowitą dodatnią - jego wiek, liczony w latach. Wąż, w zależności od swojego wieku, pozostawia inny ślad wśród piasków na brzegach rzeki płynącej przez dżunglę. Ślad jednorocznego, dwuletniego i trzyletniego węża przedstawione są na ilustracji poniżej:

 

 

Jednoroczny wąż pozostawia ślad będący łamaną, składającą się z odcinka $ [(0,0), (1,0)] $ oraz odcinka $ [(1,0), (1,1)] $.

Ślad węża o wieku $ n $ (dla $ 2 \leq n $) składa się ze śladu węża o wieku $ n-1 $, obróconego o $ 180 $ stopni śladu węża o wieku $ n-1 $ powiększonego dwukrotnie i śladu węża o wieku $ n-1 $ odbitego w symetrii względem osi OY. Kolejne ślady połączone są: koniec poprzedniego - początek następnego.

Badaczy zastanawia, w którym miejscu znajduje się pewna określona część wężowego śladu. To jest, mając daną długość $ d $ na śladzie węża, pytamy się, jakie będą współrzędne punktu, który jest oddalony od $ (0,0) $ o $ d $ licząc po śladzie węża. (Na przykład dla węża jednorocznego punkt oddalony o $ 1.5 $ ma współrzędne $ (1,0.5)) $.

Wejście:

Pierwsza linia wejścia zawiera dwie liczby całkowite $ n $ oraz $ d $ - odpowiednio liczba lat węża, o którego ślad pytamy, oraz odległość punktu, o który pytamy, od początku wężośladu. ($ 1 \leq n \leq 25 $). Możesz założyć, że punkt odległy o $ d $ od początku wężośladu leży na tym śladzie (inaczej mówiąc $ d $ jest nie większe od długości śladu). 

Wyjście:

Wyjście powinno zawierać dwie liczby całkowite - współrzędne punktu oddalonego od początku wężośladu o $ d $.

Przykład:

Wejście:

1 1

Wyjście:

1 0

Przykład:

Wejście:

2 6

Wyjście:

-1 -1

 

 

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
PozycjaImię i nazwiskoWynikCzasWężoślad
1Witold Długosz1007:33:0310
2Damian Straszak1014:09:3110
3Wojciech Szałapski1083:20:3110
4Kamil Dębowski10126:13:1310
5Wojtek Nadara10135:20:4510
6Piotr Bejda10159:29:0110
4
Twoja ocena: Brak Ocena: 4 (2 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com