← 返回题目列表

AtCoder · ddcc2019_final_e

E. 装修

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

配点: 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