Konstrukcija
레이팅 미적용의견: 0
1 sekun\(da / 512\) M\(iB / 110\) points
Let \(G\) be a directed acyclic graph. If \(c\)1, c2, c3, . . . 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@@RISE_MATH_BLOCK_0@@n\), we say that array
\(C\) = (\(c\)1, c2, c3, . . . c\(n\)) is an ordered array starting at \(c\)1 and ending at \(c@@RISE_MATH_BLOCK_1@@i\) and \(c@@RISE_MATH_BLOCK_2@@i\) to \(c\)\(i+1\).
For this definition of an ordered array \(C\) = (\(c\)1, c2, c3, . . . 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, c2, c3, . . . c\(n\)) we can define its sign as sgn(\(C\)) = (−1){len}{C}. 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) = ^{P}
{C}{S} {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 1000 vertices and
at most 1000 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\).
Subtask
Score
Constraints
1
15
\(1 \le K < 500\)
2
15
−\(300 < K \le 1\)
3
20
|\(K\)| < 10000
4
60
No additional constraints.
1 sekun\(da / 512\) M\(iB / 110\) points
The first line contains an integer \(K\) (|\(K\)| ≤\(10^{18}\)) from the task description.
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 1000\)), and the number of
edges with \(M\) (\(0 \le M \le 1000\)).
In the \(i-th\) of the next \(M\) lines you should output two distinct integers \(X@@RISE_MATH_BLOCK_0@@i\) (\(1 \le X@@RISE_MATH_BLOCK_1@@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.
06 6
1 4
1 5
4 3
5 3
3 2
2 611 026 8
1 2
1 3
1 4
1 5
5 4
2 6
3 6
4 6Clarification of the first example: 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.
평가 및 의견
Konstrukcija
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Konstrukcija