Greetings stranger!
Welcome to the land of Valyria, where dragons are still alive and there's knights fighting them!
This story is about a lonely dragon who needs to collect all of the eggs to let the kind survive.
You are the last one, and your job is to move from the West Island to East Mountains, where the
dragons are born. Beware of the holy knights, who are right behind you. In order to avoid
extermination, you are only allowed to travel from west to east during the first part of your
journey. Only once you reach the East Mountains, strengthened by your newborn sisters and
brothers you'll be able to move west to collect the remaining eggs and return back to the West
Island; you can _only_ move west during the second part of your journey.
Oh, one more thing... you need to choose the optimal path.
Technical specification:
Input:
The first line of input contains a single integer `s`, which denotes the MT19937 PRNG seed, used
to generate further input coordinates. The second line of input contains a single integer `n`,
which denotes the number of different places you need to visit. The third line of input contains
two integers m_x and m_y, which describe the dimensions of the world map (width and height,
respectively).
Coordinates are generated by the PRNG in the following order: x_0, y_0, x_1, y_1, ..., x_n-1,
y_n-1. A modulo operation is applied on each coordinate immediately after its generation:
x_i = x_i mod m_x, y_i = y_i mod m_y. If a freshly generated x_k coordinate is found to be a
duplicate of one already present on the map, it is then generated again, until a unique coordinate
is found.
Given these egg locations with different x coordinates, the West Island is the westernmost one
(smallest x), and the East Mountains is the eastermost one (largest x). The West Island is the
starting and ending point of the journey, which should consist of a set of moves towards the east,
eventually reaching the East Mountains, followed by a set of moves back towards the west,
eventually reaching the West Island. All locations except for the West Island should be visited
exactly once, and the overall length of the path should be minimized.
Output:
x_a y_a West Island coordinates (the westernmost object on the map)
...
x_k y_k East Mountains coordinates (the easternmost object on the map)
...
x_b y_b West Island coordinates.
Correct output contains n+1 lines, where each line specifies the (x, y) coordinates of a location
visited during the journey. For each i < k, x_i < x_i+1. For each i >= k, x_i > x_i+1. The sum of
distances between all adjacent pairs of coordinates must be minimal, as measured in Euclidean
metric.
2441246117
3
10 10