P13372 [GCJ 2011 #1C] Space Emergency

太空中发生了紧急情况！你需要尽快将你的舰队旗舰从恒星 $0$ 送到恒星 $N$，途中必须按编号递增顺序依次经过所有恒星（$0 \rightarrow 1 \rightarrow \ldots \rightarrow N$）。你的旗舰通常以 $0.5$ 秒差距每小时的速度航行。 除了派出旗舰外，你还可以命令工程师在不同的恒星上建造最多 $L$ 个加速器。建造一个加速器需要 $t$ 小时，所有 $L$ 个加速器可以并行建造。当你的旗舰从一个已完成加速器的恒星出发前往下一个恒星时，它的速度将提升为 $1$ 秒差距每小时。 如果旗舰在从某个恒星前往下一个恒星的途中，该恒星上的加速器建造完成，那么旗舰会在加速器完成的瞬间开始以更快的速度前进。 如果你合理建造加速器，使旗舰尽快到达恒星 $N$，那么旗舰需要多少小时才能到达？

输入的第一行为测试用例数 $T$。接下来的 $T$ 行，每行包含整数 $L$、$t$、$N$ 和 $C$，后跟 $C$ 个整数 $a_i$，所有数值以空格分隔。$a_i$ 表示对于所有整数 $k$，从恒星 $k\times C+i$ 到恒星 $k\times C+i+1$ 之间的距离（单位为秒差距）。 例如，若 $N=8$，$C=3$，$a_0=3$，$a_1=5$，$a_2=4$，则各段距离为 $[3, 5, 4, 3, 5, 4, 3, 5]$。

对于每个测试用例，输出一行，格式为 "Case #$x$: $y$"，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是旗舰到达恒星 $N$ 所需的总小时数。保证答案总是整数。

**说明** 在第二个测试用例中，我们可以建造一个加速器。两段距离分别为 $[10, 4]$。我们在第一个恒星建造加速器。经过 $4$ 小时，旗舰已前进 $2$ 秒差距，此时加速器建造完成。旗舰再用 $8$ 小时到达恒星 $1$，然后再用 $8$ 小时到达目的地恒星 $2$。 注意：本题设定的宇宙中，光速远大于 $1$ 秒差距每小时，因此无需考虑相对论效应。 **数据范围** - $1 \leq T \leq 100$。 - $1 \leq C \leq 1000$。 - $C \leq N$。 - $1 \leq a_i \leq 10^4$。 - $0 \leq t \leq 10^{11}$。 - $t$ 为偶数。 **小数据范围（12 分，测试集 1 - 可见）** - $1 \leq N \leq 1000$。 - $0 \leq L \leq 2$。 - 时间限制：3 秒。 **大数据范围（25 分，测试集 2 - 隐藏）** - $1 \leq N \leq 10^6$。 - $0 \leq L \leq N$。 - 时间限制：6 秒。 由 ChatGPT 4.1 翻译