← 返回题目列表

AtCoder · arc004_2

B. 两点之间的最大和最小距离(最大和最小)

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

問題文

在飞机上 有 N+1 点,每个点都有 它们的编号最大为 0 它们的编号最大为 N 。
我不知道每个点的位置,但是 小于0 以上 N 的整数 i ,i 点和 点的距离 i+1 点号距离 d_i 是已知的。 找到点
0 点和 点的距离 N 之间距离的最大和最小可能值。

入力

输入将以以下格式从标准输入提供。
N
d_{0}
d_{1}
:
d_{N-1}
  • 输入是 由 N+1 行组成。
  • 1 表示最大点数的整数位于第行。 N(1≦N≦500) 。 来自行
  • 2 从行 N+1至行 i+2 行目 (0 ≦ i < N)有i 一个整数,表示编号为 i+1 的点的距离 d_i(1≦d_i≦30,000) 。 来自行

出力

输出到标准输出, 输出编号为2 行组成。
1 第几行包含,0 点和 点的距离 N 的点的最大可能距离。 输出编号为
2 第几行包含,0 点和 点的距离 N 的点的最小可能距离。
误差至少是绝对误差和相对误差之一。 10^{-3} 如果低于则允许。
请在末尾输出换行符。

入力例 1

1
1024

出力例 1

1024
1024
  • 来自输入 有编号为 0 点和 点的距离 1 的点,它们之间的距离为 事实证明 1024 。
  • 所需的距离是 由于它是编号为0 点和 点的距离 1 的点之间的距离,因此最大值和最小值均为 编号为 1024 。

入力例 2

3
3
4
5

出力例 2

12
0
  • 0 点和 点的距离 3 的点之间的距离最大,如下图(a)所示。 以编号为 0 点和 点的距离 3 的点为结束 4 当点排成一条直线时,距离为 编号为 3+4+5=12 。
  • 0 点和 点的距离 3 的点之间的距离最小,如下图(b)所示。 如果编号为 0 点和 点的距离 3 的点的位置相等,则距离为 编号为 0 。

入力例 3

2
512
512

出力例 3

1024
0
  • 0 点和 点的距离 2 的点之间的距离最大,如下图(a)所示。 以编号为 0 点和 点的距离 2 的点为结束 3 当点排成一条直线时,距离为 编号为 512+512=1024 。
  • 0 点和 点的距离 2 的点之间的距离最小,如下图(b)所示。 如果编号为 0 点和 点的距离 2 的点的位置相等,则距离为 编号为 0 。

入力例 4

3
4
8
1

出力例 4

13
3
  • 0 点和 点的距离 3 的点之间的距离最大,如下图(a)所示。 以编号为 0 点和 点的距离 3 的点为结束 4 当点排成一条直线时,距离为 编号为 4+8+1=13 。
  • 0 点和 点的距离 3 的点不能重叠,因此 编号为0 点和 点的距离 3 的点之间的距离最小,如下图(b)所示。 在连接编号为 1 点和 点的距离 2 的点的线段上 如果有一个编号为 0 点和 点的距离 3 的点,则距离为 编号为 8-4-1=3 。

入力例 5

10
1
2
3
4
5
6
7
8
9
10

出力例 5

55
0
  • 0 点和 点的距离 10 的点之间的距离最大。 从点0 当编号为 10 的点排成一直线时,距离为 编号为 1+2+3+4+5+6+7+8+9+10=55 。
  • 0 点和 点的距离 10 的点之间的距离最小的示例是 按顺序排成一圈,直到编号为0 当编号为 10 的点, 这是当编号为0 点和 点的距离 10 的点的位置相等时的情况。