D - All Your Paths are Different Lengths Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 700 点

問題文

整数 L が与えられます。以下の条件を満たす有向グラフをひとつ構成してください。構成したグラフに多重辺が含まれていても構いません。 なお、条件を満たす有向グラフは必ず存在することが証明できます。

  • 頂点数 N は 20 以下で、すべての頂点には 1 以上 N 以下の相異なる番号が付けられている
  • 辺数 M は 60 以下で、すべての辺には 0 以上 10^6 以下の整数の長さが付けられている
  • 全ての辺は番号の小さい方の頂点から大きい方の頂点に向かって向きづけられている。すなわち、1,2,...,N はこのグラフの頂点の番号を適当なトポロジカル順序で並べてできる列である
  • 頂点 1 から頂点 N への異なるパスはちょうど L 個あり、それらの長さは 0 から L-1 までの相異なる整数である

ただし、パスの長さとは、そのパス上の辺の長さの和を表します。また、2 つのパスが異なるとは、パス上の辺の集合が異なることを指します。

制約

  • 2 \leq L \leq 10^6
  • L は整数である

入力

入力は以下の形式で標準入力から与えられる。

L

出力

1 行目には、構成したグラフの頂点数 N と辺数 M を出力せよ。 続く M 行のうちの i 行目には、3 つの整数 u_i,v_i,w_i を出力せよ。これらはそれぞれ、i 本目の辺の始点、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

出力例のグラフには 頂点 1 から N=8 への 4 本のパスがあり、

  • パス 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

Score : 700 points

Problem Statement

You are given an integer L. Construct a directed graph that satisfies the conditions below. The graph may contain multiple edges between the same pair of vertices. It can be proved that such a graph always exists.

  • The number of vertices, N, is at most 20. The vertices are given ID numbers from 1 to N.
  • The number of edges, M, is at most 60. Each edge has an integer length between 0 and 10^6 (inclusive).
  • Every edge is directed from the vertex with the smaller ID to the vertex with the larger ID. That is, 1,2,...,N is one possible topological order of the vertices.
  • There are exactly L different paths from Vertex 1 to Vertex N. The lengths of these paths are all different, and they are integers between 0 and L-1.

Here, the length of a path is the sum of the lengths of the edges contained in that path, and two paths are considered different when the sets of the edges contained in those paths are different.

Constraints

  • 2 \leq L \leq 10^6
  • L is an integer.

Input

Input is given from Standard Input in the following format:

L

Output

In the first line, print N and M, the number of the vertices and edges in your graph. In the i-th of the following M lines, print three integers u_i,v_i and w_i, representing the starting vertex, the ending vertex and the length of the i-th edge. If there are multiple solutions, any of them will be accepted.

Sample Input 1

4

Sample Output 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

In the graph represented by the sample output, there are four paths from Vertex 1 to N=8:

  • 1 → 2 → 3 → 4 → 8 with length 0
  • 1 → 2 → 3 → 7 → 8 with length 1
  • 1 → 2 → 6 → 7 → 8 with length 2
  • 1 → 5 → 6 → 7 → 8 with length 3

There are other possible solutions.

Sample Input 2

5

Sample Output 2

5 7
1 2 0
2 3 1
3 4 0
4 5 0
2 4 0
1 3 3
3 5 1