P2583 [ICPC 2003 WF] Subway Spy

# Description Agent Maria has been sent to city S to carry out a particularly dangerous mission. She must use the subway to complete her task; city S has only one subway line in operation, so it is not complicated. The current time is $0$. Maria starts from station $1$ and must meet the spy at the last station exactly at time $T$. She knows a powerful organization is tracking her. If she stays at a station, she faces a high risk of being caught; hiding in a moving train is safer. Therefore, she decides to stay on moving trains as much as possible, and she can ride only along the line in either direction (forward or backward). To arrive at the last station on time and safely, Maria needs a plan that minimizes the total time she waits at stations. You must write a program to find Maria’s minimal total waiting time. Of course, if she arrives at the terminal earlier than the required time, she can wait at the station for the contact; this waiting time must also be counted. There are $n$ stations, numbered $1 \sim n$. Trains shuttle along the line: either from station $1$ to station $n$, or from station $n$ back to station $1$. The travel time between any two consecutive stations is fixed, dwell times can be ignored, and Maria is extremely fast, so she can board or alight instantly, even if two trains arrive simultaneously.

特工玛利亚被送到 S 市执行一个特别危险的任务。她需要利用地铁完成他的任务，S 市的地铁只有一条线路运行，所以并不复杂。 玛利亚有一个任务，现在的时间为 $0$，她要从第一个站出发，并在最后一站的间谍碰头。玛利亚知道有一个强大的组织正在追踪她，她知道如果一直呆在一个车站，她会有很大的被抓的风险，躲在运行的列车中是比较安全的。所以，她决定尽可能地呆在运行的列车中，她只能往前或往后坐车。 玛利亚为了能准时且安全的到达最后一个车站与对方碰头，需要知道在在车站最小等待时间总和的计划。你必须写一个程序，得到玛丽亚最短的等待时间。当然，到了终点站之后如果时间还没有到规定的时刻，她可以在车站里等着对方，只不过这个等待的时刻也是要算进去的。 这个城市有 $n$ 个车站，编号是 $1\sim n$，火车是这么移动的：从第一个车站开到最后一个车站。或者从最后一站发车然后开会来。火车在每特定两站之间行驶的时间是固定的，我们也可以忽略停车的时间，玛利亚的速度极快，所以他可以迅速上下车即使两辆车同时到站。

输入文件包含多组数据，每组数据都由 $7$ 行组成。 - 第 $1$ 行一个正整数 $N\ (2 \le N \le 50)$ 表示站的数量。 - 第 $2$ 行一个正整数 $T\ (0 \le T \le 2000)$ 表示需要的碰头时间。 - 第 $3$ 行 $1\sim n-1$ 个正整数 $t_i\ (0

For each dataset, print one line $\text{\texttt{Case Number }\textit{N}\texttt{:}}$ (where $N$ starts from $1$) followed by an integer denoting the minimal total waiting time, or the word $\verb!impossible!$ if Maria cannot accomplish the task. See the sample output.

Explanation for Sample 1: She boards at minute $0$, gets off at station $3$, immediately takes the train that left at minute $0$ and departs at minute $15$ to go back, gets to station $2$, immediately takes the train that started at minute $20$ and departs at minute $25$ to the terminal, arrives at minute $50$, and then needs to wait $5$ minutes. Translated by ChatGPT 5