QOJ.ac

QOJ

実行時間制限: 6 s メモリ制限: 2048 MB 満点: 100

#2417. 高度剖面

統計

经典的自行车赛“阿姆斯特尔黄金赛”(Amstel Gold Race)每年在荷兰林堡省举行。比赛中频繁出现的短坡让参赛者几乎没有时间在坡间恢复体力。例如,比赛最后 42 公里的路程中就有 8 个平均长度约为 1 公里的陡坡。

每段爬坡的坡度以百分比给出。100% 的坡度意味着每前进 1 水平米,海拔上升 1 米。0% 的坡度表示完全平坦。通常情况下,$p\%$ 的坡度意味着每前进 1 水平米,海拔上升 $p/100$ 米。注意,坡度也可以是负数。

已知比赛起点后每个整数水平公里处路面的海拔高度,为简化起见,我们假设这些点之间的海拔高度呈分段线性变化。换句话说,坡度在 0 到 1 公里之间、1 到 2 公里之间等区间内保持恒定。例如,在图 H.1 中,水平距离 2.5 公里处的海拔高度正好是 20 米。

图 H.1:样例输入 1 的示意图。前 3 个水平公里的坡度依次为 0%、1% 和 2%。最后一公里的坡度为 $-3.5\%$。

阿姆斯特尔黄金赛无法与环法自行车赛或环意大利自行车赛中的某些丘陵赛段相提并论,但你仍然对它们之间的比较感兴趣。对于每一场单日赛,无论是阿姆斯特尔黄金赛还是环法自行车赛的某个赛段,你都想知道坡度至少达到给定值的最长水平区间的长度。实际上,你需要求出多个坡度对应的答案。

水平区间的坡度是在两个端点之间测量的。例如,图 H.1 中比赛在 1 公里到 4 公里之间的坡度为 2%,因为在 2 公里的水平距离内海拔上升了 60 米。该水平区间也是坡度至少为 2% 的最长区间。

输入格式

输入包含: 一行,包含两个整数 $n$ 和 $k$ ($2 \le n \le 10^5$, $1 \le k \le 50$),分别表示比赛的水平长度(单位:公里)和你需要查询的坡度数量。 一行,包含 $n + 1$ 个整数 $h_0, h_1, \dots, h_n$ ($0 \le h_i \le 10^9$),其中 $h_i$ 表示从起点出发 $i$ 水平公里处的路面海拔高度(单位:米)。 * $k$ 行,每行包含一个实数 $g$ ($-100 \le g \le 100$,且 $g$ 的小数点后恰好有一位数字),表示你关心的坡度。

输出格式

对于输入的每个坡度 $g$,按输入顺序输出坡度至少为 $g$ 的最长水平区间的长度(单位:公里)。如果不存在合适的区间,输出 “impossible”。

你的答案应具有不超过 $10^{-6}$ 的绝对或相对误差。

样例

样例输入 1

8 2
0 0 10 30 60 45 75 65 30
2.0
3.1

样例输出 1

3.000000000
impossible

样例输入 2

2 2
0 30 30
3.0
2.0

样例输出 2

1.000000000
1.500000000

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.