E - 飾りつけ (Decoration)

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 1200

問題文

来年で設立 80 周年を迎える D 社は、記念としてオフィスの前にグラフを飾ることにしました。
このグラフは、以下の条件を満たす必要があります。

  • 重み付き有向グラフである。
  • 頂点の数を N、辺の数を M として、頂点は 1, 2, 3, ..., N と番号付けられている。
  • N \leq 70 である。
  • i 本目の辺が頂点 u_i から v_i への重み w_i の有向辺であるとすると、u_i < v_i, 0 \leq w_i \leq 2 \ 000 (w_i は整数) である。また、i \neq j ならば (u_i, v_i) \neq (u_j, v_j) である。
  • 頂点 1 から N へのどのパスの長さも、p_1, p_2, p_3, ..., p_Q のいずれかである。なお、パスの長さとは、そのパスに含まれる辺の重みの総和である。
  • 頂点 1 から N へのパスのうち、長さがちょうど p_1 であるものが 1 個以上、長さがちょうど p_2 であるものが 1 個以上、長さがちょうど p_3 であるものが 1 個以上、…、長さがちょうど p_Q であるものが 1 個以上存在する。

このようなグラフを 1 個構築してください。
頂点数が少ないほど、飾りつけにかかる費用が減るので社長も喜ぶでしょう。

制約

  • 1 \leq Q \leq 2 \ 000
  • 1 \leq p_1 < p_2 < p_3 < ... < p_Q \leq 2 \ 000
  • 入力値はすべて整数

得点

提出の得点は、以下のように計算される。

  • 一つのテストケースでも不正解であった場合、その提出の得点は 0 点となる。
  • すべてのテストケースに正解した場合、それらに対して用いられた N の最大値を L として、提出の得点は以下のように決定される。
    • 66 \leq L \leq 70 のとき、600
    • 61 \leq L \leq 65 のとき、800
    • 54 \leq L \leq 60 のとき、990 + 30 \times (60 - L)
    • L \leq 53 のとき、1200

なお、この問題の制約下で、任意の入力に対して N \leq 53 であるような条件を満たすグラフが必ず存在することが証明できる。


入力

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

Q
p_1 p_2 p_3 ... p_Q

出力

条件を満たすグラフの一つを以下の形式で出力せよ。

N M
u_1 v_1 w_1
u_2 v_2 w_2
u_3 v_3 w_3
:
u_M v_M w_M

条件を満たすグラフが複数存在する場合は、そのうちのどれを出力しても正解となる。


入力例 1

3
1 2 5

出力例 1

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

この出力は、以下のグラフに対応します。

頂点 1 から N = 5 へのパスは以下の 3 通りです。

  • 125: 長さ 1 + 0 = 1
  • 135: 長さ 2 + 0 = 2
  • 145: 長さ 5 + 0 = 5

これらは、Q = 3, p_1 = 1, p_2 = 2, p_3 = 5 に対して問題文中の条件を満たします。
この出力の他に、例えば以下の出力も正解となります。

4 6
1 2 1
1 3 4
1 4 1
2 3 3
2 4 1
3 4 1

入力例 2

4
1 2 3 4

出力例 2

5 10
1 2 1
1 3 1
1 4 1
1 5 1
2 3 1
2 4 1
2 5 1
3 4 1
3 5 1
4 5 1

入力例 3

7
1 3 7 9 11 14 16

出力例 3

8 15
1 2 1
1 3 2
1 4 3
5 8 0
6 8 0
7 8 0
2 5 0
2 6 2
2 7 6
3 5 7
3 6 9
3 7 12
4 5 13
4 6 8
4 7 6