AT_ddcc2019_final_e 飾りつけ (Decoration)

即将迎来成立 80 周年的 D 公司决定在办公室前展示一幅图作为纪念。这个图需要满足以下条件： - 它是一个带权有向图。 - 图中有 $N$ 个顶点和 $M$ 条边，顶点编号依次为 $1, 2, 3, \ldots, N$。 - $N$ 的值不超过 70。 - 每条边从顶点 $u_i$ 指向顶点 $v_i$，有权重 $w_i$，并且满足 $u_i < v_i$，且 $0 \leq w_i \leq 2000$，$w_i$ 是一个整数。此外，对于不同的边 $i$ 和 $j$，如果 $i \neq j$，那么 $(u_i, v_i)$ 不能相同。 - 从顶点 $1$ 到顶点 $N$ 的所有路径，其长度（路径中所有边的权重和）必须是给定数值 $p_1, p_2, p_3, \ldots, p_Q$ 中的某一个。 - 从顶点 $1$ 到顶点 $N$ 的路径中，长度恰好为 $p_1$ 的路径至少有一条，长度恰好为 $p_2$ 的路径至少有一条，以此类推，直到 $p_Q$。 请构建一个满足上述要求的图。公司希望顶点数量越少越好，因为这会降低装饰成本。

输入数据从标准输入读取，格式如下： > $Q$ $p_1$ $p_2$ $p_3$ $\ldots$ $p_Q$

输出一个满足条件的图，格式如下： > $N$ $M$ $u_1$ $v_1$ $w_1$ $u_2$ $v_2$ $w_2$ $u_3$ $v_3$ $w_3$ $\ldots$ $u_M$ $v_M$ $w_M$ 如果有多个符合条件的图，你可以输出任意一个。

### 约束 - $1 \leq Q \leq 2000$ - $1 \leq p_1 < p_2 < p_3 < \ldots < p_Q \leq 2000$ - 所有输入值均为整数 ### 得分 您的得分依据以下规则计算： - 如果某个测试用例不满足条件，该提交的得分为 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$ 的图。 ### 示例解释 示例输出对应的图如下： 从顶点 $1$ 到 $N = 5$ 的路径有以下三种： - 路径 $1 \to 2 \to 5$，长度为 $1 + 0 = 1$。 - 路径 $1 \to 3 \to 5$，长度为 $2 + 0 = 2$。 - 路径 $1 \to 4 \to 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 ``` **本翻译由 AI 自动生成**