ZOJ Problem Set - 2696
Designing computer chips is quite difficult. Recently Peter has decided to get a job in Karelia Quaterconductors company that is going to produce chips for new EBM processor. As a qualifying work for the position he has got a task of designing a layout for a very simple chip. A chip has n inputs and n outputs, located in points (0, 0) , (1, 0) , , (n-1, 0) and (0, 1) , (1, 1) , , (n-1, 1) respectively (all dimensions are, of course, in nanometers).
In this chip the i-th input must be connected to the ai-th output using nanowires. All nanowires must be polylines with segments parallel to the sides of the chip (coordinate axes). No two nanowires must intersect (there must be no common point for any two nanowires). The thickness of the wires is so small, that it can be ignored.
Help Peter to get the job, write a program that will design the chip for him.
There are mutilple cases in the input file.
The first line of each case contains n (1 <= n <= 10 ). Next line contains n different integer numbers --- a1, a2, , an.
There is an empty line after each case.
Output the description of n nanowires. Each description must start with k --- the number of segments in the wire (k must not exceed 1000). Next k + 1 lines must contain two numbers each and specify the coordinates of the breaking points of the polyline. All coordinates must be specified as rational irreducible fractions in a form nominator/ denominator. Nominator and denominator must not exceed 109 .
The first point of the i-th polyline must be the i-th input of the chip and its last point must be the ai-th output of the chip.
There should be an empty line after each case.
2 2 1
3 0/1 0/1 0/1 1/2 1/1 1/2 1/1 1/1 4 1/1 0/1 3/2 0/1 3/2 3/2 0/1 3/2 0/1 1/1
Source: Andrew Stankevich's Contest #9