Runda 13 [Hard] - Wężoślad
28.02.2011 - Damian Rusak
Zadanie tygodnia runda 13; kategoria Hard Limit czasowy: 1s; Limit pamięciowy: 64MB WężośladGrupa 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 oraz odcinka . Ślad węża o wieku (dla ) składa się ze śladu węża o wieku , obróconego o stopni śladu węża o wieku powiększonego dwukrotnie i śladu węża o wieku 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ść na śladzie węża, pytamy się, jakie będą współrzędne punktu, który jest oddalony od o licząc po śladzie węża. (Na przykład dla węża jednorocznego punkt oddalony o ma współrzędne . Wejście: Pierwsza linia wejścia zawiera dwie liczby całkowite oraz - odpowiednio liczba lat węża, o którego ślad pytamy, oraz odległość punktu, o który pytamy, od początku wężośladu. (). Możesz założyć, że punkt odległy o od początku wężośladu leży na tym śladzie (inaczej mówiąc 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 . 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.
(2 ocen) |
Copyright © 2008-2010 Wrocławski Portal Informatyczny
design: rafalpolito.com