配点: 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 是的。
- 1 → 2 → 5:长度 1 + 0 = 1
- 1 → 3 → 5:长度 2 + 0 = 2
- 1 → 4 → 5:长度 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