← 返回题目列表

AtCoder · arc102_b

D. 你所有的路径长度都不同

中文机器翻译题面 查看原题

分数: 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