Suppose we number the four quadrants on the coordinate plane as follows.

2 | 1 | --------------+-------------- | 3 | 4

We are given a sequence over {1,2,3,4}, e.g. 1244112431. This specifies an order in which the quadrants are to be visited --- we have to first move to quadrant 1, then quadrant 2, then quadrant 4, then stay in quadrant 4, ....

This tour consists of N stops, q1q2...qN. We are then provided with 2N distinct postive integers d1,d2,...,d2N. (N is in the range [1..10000].)

The tour starts at (0,0). We now have to group the 2N numbers into N pairs (x1,y1), (x2,y2), ..., (xN,yN). We can insert negative signs, if required, before each xi or yi.

Intepret these pairs as displacements. This constructs a tour as follows.

Point Current Quadrant p0 (0,0) p1 (x1,y1) v1 p2 (x1+x2,y1+y2) v2 p3 (x1+..+x3,y1+..+y3) v3 . . . pN (x1+..+xN,y1+..+yN) vN

The goal is to make the sequence of quadrants visited v1v2...vN equal to the original sequence q1q2...qN.

For instance, suppose the desired trajectory is 4 1 2 1 and there are 8 numbers 7, 5, 6, 1, 3, 2, 4, 8, here is a solution:

(+7,-1), (-5,+2), (-4,+3), (+8,+6)

©IARCS 2012–2016

PÄ›stujeme web | visit: Skluzavky