Indian Computing Olympiad

Sorting→Utopia (IOI 2002)

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)
      

Solution

---