COCI '19 Contest 6 #3 Konstrukcija

View as PDF

Submit solution


Points: 20 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem types

Let G be a directed acyclic graph. If c_1, c_2, \dots, c_n are distinct vertices of G such that there is a path from c_1 to c_2, there is a path from c_2 to c_3, …, and there is a path from c_{n-1} to c_n, we say that array C = (c_1, c_2, \dots, c_n) is an ordered array starting at c_1 and ending at c_n. Note that between neighbouring elements c_i and c_{i+1} of ordered array C it isn't necessary to exist a direct edge, it is enough for the path to exist from c_i to c_{i+1}.

For this definition of an ordered array C = (c_1, c_2, \dots, c_n), we define its length len(C) = n. Therefore, the length of an ordered array is equal to the number of vertices it holds. Note that the ordered array can have a length of 1 when holding a single vertex which represents both its beginning and its end.

Also, for an ordered array C = (c_1, c_2, \dots, c_n) we can define its sign as sgn(C) = (-1)^{len(C)+1}. For vertices x and y of G, let's denote with S_{x,y} a set of all ordered arrays that start in x and end in y.

Finally, we define the tension between nodes x and y as tns(x, y) = \sum_{C \in S_{x,y}} sgn(C). Therefore, the tension between nodes x and y equals the sum of signs of all ordered arrays that start in x and end in y.

An integer K is given. Your task is to construct a directed acyclic graph with at most 1\,000 vertices and at most 1\,000 edges for which tns(1, N) = K holds. Number N in the previous expression denotes the number of vertices in a graph. Vertices of a graph should be indexed using positive integers from 1 to N.

Input Specification

The first line contains an integer K (|K| \le 10^{18}) from the task description.

Output Specification

In the first line you should output the number of vertices and the number of edges of the constructed graph. Let's denote the number of vertices of that graph with N (1 \le N \le 1\,000), and the number of edges with M (0 \le M \le 1\,000).

In the i-th of the next M lines you should output two distinct integers X_i and Y_i (1 \le X_i, Y_i \le N), which represent the i-th edge which is directed from vertex with index X_i towards vertex with index Y_i. Each edge must appear only once in the output.

Also, the absolute value of tension between each two nodes in the graph must be less or equal to 2^{80}. If there are multiple solutions, output any of them.

Constraints

SubtaskPointsConstraints
1151 \le K < 500
215-300 < K \le -1
320|K| < 10\,000
460No additional constraints.

Sample Input 1

0

Sample Output 1

6 6
1 4
1 5
4 3
5 3
3 2
2 6

Explanation of Sample Output 1

The constructed graph has 6 vertices. Ordered arrays that start in 1 and end in 6 are: (1, 6), (1, 4, 6), (1, 5, 6), (1, 3, 6), (1, 2, 6), (1, 4, 3, 6), (1, 4, 2, 6), (1, 5, 3, 6),
(1, 5, 2, 6), (1, 3, 2, 6), (1, 4, 3, 2, 6), (1, 5, 3, 2, 6). Their lengths are (in order): 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, so their signs are -1, 1, 1, 1, 1, -1, -1, -1, -1, -1, 1, 1. Therefore, the tension between 1 and 6 is equal to -1 + 1 + 1 + 1 + 1 - 1 - 1 - 1 - 1 - 1 + 1 + 1 = 0.

Sample Input 2

1

Sample Output 2

1 0

Sample Input 3

2

Sample Output 3

6 8
1 2
1 3
1 4
1 5
5 4
2 6
3 6
4 6

Comments

There are no comments at the moment.