In the event of technical difficulties with Szkopuł, please contact us via email at firstname.lastname@example.org.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (
#szkopul channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
Lets consider a set of vertical segments on the plain (segments include their end points). None of the elements of have a point in common. Two segments are said to "see each other" if there exists a horizontal segment, which connects them and does not have any common points with other segments from .
On the figure below, there is an example set of segments. Pairs of segments that can see each other, are: 1-2, 1-3, 2-3, 1-5 and 4-5. The segments 1 and 4 do not see each other.
For a given number , we search for a set of vertical segments such that the number of pairs of segments which can see each other is as big as possible.
Write a program which:
The first and only line of the standard input contains one integer ().
The first line of the standard output should contain one integer - maximal number of pairs of segments that can see each other. Each of the following lines should identify the coordinates of one segment. Line (for ) consists of three integers: , i (, ), separated by a single space. They represent the segment which connects the points and .
If there are more than one correct arrangement of segments, your program can write out any of them.
For the input data:
the correct result is:
6 1 1 5 2 2 4 3 3 5 4 1 4
Task author: Jakub Radoszewski.