eolymp
bolt
Try our new interface for solving problems
Məsələlər

Кривая дракона High

Кривая дракона High

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Кривая дракона – это бесконечная ломаная из звеньев единичной длины, которая строится следующим образом. Выбирается некоторая точка на плоскости (например, точка (0, 0)) и одно из четырех направлений, параллельных координатным осям. Левый (правый) дракон порядка n строится так:

  • если n равно 0, то отложить отрезок длины 1 от текущей точки в текущем направлении, переместившись в конечную точку;

  • в противном случае построить левого дракона порядка n-1 от текущей точки в текущем направлении, повернуться на 90 градусов налево (направо) в его конечной точке и построить правого дракона порядка n-1.

Поскольку левый дракон порядка n содержит в качестве своего начала левого дракона порядка n-1, то вполне корректно определяется левый дракон бесконечного порядка. Именно эта ломаная и называется кривой дракона.

Построим из точки (0, 0) кривые дракона во всех четырех направлениях. Есть теорема, доказанная Д.Кнутом, о том, что эти кривые не пересекаются (за исключением касания в вершинах) и полностью покрывают целочисленную сетку на плоскости. В данной задаче от вас потребуется проверить эту теорему, а именно по заданному единичному отрезку сетки определить какому из четырех драконов он принадлежит.

Giriş verilənləri

В единственной строке входного файла задаются 4 целых числа: две координаты одного конца некоторого отрезка, параллельного одной из осей координат, и две координаты другого конца.

Все числа не превышают по модулю 10^9. Расстояние между точкам равно 1.

Çıxış verilənləri

В первой строке выходного файла выведите номер драконовой кривой, которой принадлежит соответствующее звено (1 – дракон, отложенный в положительном направлении оси Ox, 2 – в положительном направлении оси Oy, 3 – в отрицательном направлении оси Ox, 4 – в отрицательном направлении оси Oy). Во второй строке выведите номер этого звена в соответствующей ломаной. Гарантируется, что это число не превосходит 10^12.

Nümunə

Giriş verilənləri #1
1 0 1 1
Çıxış verilənləri #1
1
2
Müəllif Неспирный В.Н.