#P6219. [COCI2019-2020#6] Konstrukcija

[COCI2019-2020#6] Konstrukcija

题目背景

题目翻译来自 LOJ3268

题目描述

译自 COCI 2019/2020 Contest #6 T3. Konstrukcija

GG 为一个有向无环图。若 GG 的不同顶点 c1,c2,c3,cnc_1,c_2,c_3,\ldots c_n 满足有一条从 c1c_1c2c_2 的路径,有一条从 c2c_2c3c_3 的路径,……还有一条从 cn1c_{n-1}cnc_n 的路径,则称数组 C=(c1,c2,c3,cn)C = (c_1,c_2,c_3,\ldots c_n) 为一个从 c1c_1 开始,在 cnc_n 结束的有序数组。
注意对于 CC 中任意的两个相邻的元素 ci,ci+1c_i,c_{i+1} 不必有直接连接的边,只需要有一条路径即可。

同时,我们定义有序数组 C=(c1,c2,c3,cn)C = (c_1,c_2,c_3,\ldots c_n) 的长度 len(C)=n\mathrm{len}(C) = n。因此,一个有序数组的长度即为其中包含的顶点个数。
注意可以存在一个长度为 11,从同一个点开始并结束的有序数组。

并且,我们再定义有序数组 C=(c1,c2,c3,cn)C = (c_1,c_2,c_3,\ldots c_n) 的符号 sgn(C)=(1)len(C)+1\mathrm{sgn}(C) = (-1)^{\mathrm{len}(C)+1}
对于 GG 中的顶点 x,yx,y,我们用 Sx,yS_{x,y} 表示所有从 xx 开始并在 yy 结束的有序数组的集合。

最后,我们定义顶点 x,yx,y 之间的矛盾值为 $\mathrm{tns}(x,y) = \sum\limits_{C \in S_{x,y}} \mathrm{sgn}(C)$。
也就是说,顶点 x,yx,y 之间的矛盾值等于所有从 xx 开始并在 yy 结束的有序数组的符号之和。

给定一个整数 KK,你需要构造一个最多 10001000 个点,10001000 条边的有向无环图满足 tns(1,N)=K\mathrm{tns}(1,N) = K,其中 NN 为顶点个数。
顶点以正整数 1N1\ldots N 编号。

输入格式

第一行,一个整数 KK

输出格式

第一行,两个整数 N,MN,M 表示你构造出的有向无环图的点数与边数。
以下 MM 行中,第 ii 行包含两个不同的整数 Xi,YiX_i,Y_i,表示第 ii 条边从 XiX_i 连向 YiY_i。每条边应最多出现一次。
并且,你的方案需要满足任意两点的矛盾值的绝对值不超过 2802^{80}
若有多解,随意输出一解即可。

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

提示

样例 1 解释

构造出的图包含 66 个顶点。从 11 开始在 66 结束的有序数组有:

  • (1,6)(1, 6)
  • (1,4,6)(1, 4, 6)
  • (1,5,6)(1, 5, 6)
  • (1,3,6)(1, 3, 6)
  • (1,2,6)(1, 2, 6)
  • (1,4,3,6)(1, 4, 3, 6)
  • (1,4,2,6)(1, 4, 2, 6)
  • (1,5,3,6)(1, 5, 3, 6)
  • (1,5,2,6)(1, 5, 2, 6)
  • (1,3,2,6)(1, 3, 2, 6)
  • (1,4,3,2,6)(1, 4, 3, 2, 6)
  • (1,5,3,2,6)(1, 5, 3, 2, 6)

它们的长度分别为 1,2,2,2,2,3,3,3,3,3,4,41, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4
所以它们的符号分别为 1,1,1,1,1,1,1,1,1,1,1,1-1, 1, 1, 1, 1,-1,-1,-1,-1,-1, 1, 1
因此,1166 的矛盾值为 1+1+1+1+111111+1+1=0-1 + 1 + 1 + 1 + 1 - 1 - 1 - 1 - 1 - 1 + 1 + 1 = 0


数据范围:

对于 100%100\% 的数据,K1018|K| \le 10^{18}
各子任务限制见下表:

子任务 分值 限制
00 为样例
11 1313 1K<5001 \le K < 500
22 300<K1-300 < K \le 1
33 1818 K<10000\lvert K\rvert < 10000
44 5656 -