#agc012e. [agc012_e]Camel and Oases

[agc012_e]Camel and Oases

给定 nn 个绿洲,第 ii 个绿洲的坐标为 xix_i ,保证 109x1<x2...<xn109-10^{9}\le x_1<x_2...<x_n\le 10^9

现在有一个人在沙漠中进行旅行,他初始的背包的水容积为 VV 升,同时他初始拥有 VV 升水 ,每次到达一个绿洲时,他拥有的水的量将自动重置为容积上限(可以使用多次)。他现在可以选择两个操作来进行旅行:

1.1. 走路,行走距离为 dd 时,需要消耗 dd 升水。清注意,任意时刻你拥有的水的数量不能为负数。

2.2. 跳跃,令 vv 为你当前拥有的水量,若 v>0v>0,则你可以跳跃至任意一个绿洲,然后重置容积上界和所拥有的水量为 v/2v/2 (向下取整)。

对于每一个 ii 满足 1in1\le i\le n ,你需要求解,当你在第 ii 个绿洲作为起点时,你能否依次遍历其他所有绿洲。如果可以,输出 Possible,否则输出 Impossible