分数: 700 点
问题陈述
给你一个整数 L。构造满足以下条件的有向图。该图可以在同一对顶点之间包含多条边。可以证明这样的图总是存在的。
- 顶点数, N,最多是 20。顶点的 ID 号来自 1 to N.
- 边数, M,最多是 60。每条边的长度介于 0 和 10^6 (含)。
- 每条边都从 ID 较小的顶点指向 ID 较大的顶点。也就是说, 1,2,...,N 是顶点的一种可能的拓扑顺序。
- 正好有 L 来自 Vertex 的不同路径 1 到顶点 N。这些路径的长度都不同,并且它们是之间的整数 0 和 L-1.
这里,路径的长度是该路径中包含的边的长度之和,并且当这两个路径中包含的边的集合不同时,两个路径被认为是不同的。
约束
- 2 \leq L \leq 10^6
- L 是一个整数。
输入
输入由标准输入按以下格式给出:
L
输出
在第一行中,打印 N 和 M,图中的顶点和边的数量。 在 i- 以下各项 M 行,打印三个整数 u_i,v_i 和 w_i,表示起始顶点、结束顶点和长度 i第边缘。 如果有多个解决方案,则任何一个都将被接受。
示例输入 1
4
示例输出 1
8 10 1 2 0 2 3 0 3 4 0 1 5 0 2 6 0 3 7 0 4 8 0 5 6 1 6 7 1 7 8 1
在示例输出表示的图中,有四个来自 Vertex 的路径 1 to N=8:
- 1 → 2 → 3 → 4 → 8 长度 0
- 1 → 2 → 3 → 7 → 8 长度 1
- 1 → 2 → 6 → 7 → 8 长度 2
- 1 → 5 → 6 → 7 → 8 长度 3
还有其他可能的解决方案。
示例输入 2
5
示例输出 2
5 7 1 2 0 2 3 1 3 4 0 4 5 0 2 4 0 1 3 3 3 5 1