Кривая дракона над Таласом


Отправить решение Решать в редакторе

Сложность: 75%
Очки: 100 (частичный балл)
Ограничение по времени: 2.0s
Ограничение по памяти: 256M

Автор:
Типы задач
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

Над Таласской долиной запускают воздушного змея-дракона, а его хвост оставляет на клетчатой карте ломаную. Ломаная начинается в точке (0, 0) и состоит из отрезков длины 1, первый отрезок идёт на восток — в точку (1, 0).

После n-го отрезка (n ≥ 1) змей поворачивает на 90°. Направление поворота определяется так: запишем n = 2^t · (2j + 1), где j и t — целые неотрицательные числа. Если j чётное, змей поворачивает налево (против часовой стрелки), если нечётное — направо.

Получается знаменитая кривая дракона (её также получают, если много раз сложить полоску бумаги пополам и развернуть её под прямыми углами).

Рисунок

Обозначим через P(N) точку, в которой окажется змей после N отрезков, P(0) = (0, 0). Ответьте на q запросов: по числу N найдите P(N).

Входные данные

В первой строке — число q (1 ≤ q ≤ 10⁵). В каждой из следующих q строк — одно целое число N (0 ≤ N ≤ 10¹⁸).

Выходные данные

Для каждого запроса выведите два целых числа — координаты x и y точки P(N). Ось x направлена на восток, ось y — на север.

Пример 1

Вход:

6
0
1
2
5
6
8

Выход:

0 0
1 0
1 1
-1 2
-1 1
-2 2

Пояснение

Первые точки ломаной: (0, 0), (1, 0), (1, 1), (0, 1), (0, 2), (−1, 2), (−1, 1), … После первого отрезка (n = 1, j = 0) змей повернул налево, после второго (n = 2, снова j = 0) — тоже налево, после третьего (n = 3, j = 1) — направо.

Система оценивания

Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 30 % тестов N ≤ 10⁶.


Комментарии

Еще нет ни одного комментария.