#P0010. 山竹 VS 桦加沙
山竹 VS 桦加沙
题目背景
超强台风桦加沙(英语:Super Typhoon Ragasa,国际编号:2518, 联合台风警报中心:24W,菲律宾大气地球物理和天文服务管理局:Nando)为2025年太平洋台风季第18个被命名的风暴。“桦加沙”一名由台风海贝思更替而来,由菲律宾提供,含义即“快速移动”;本次为“桦加沙”一名首次使用。
台风“桦加沙”于2025年9月18日晚20时在菲律宾以东洋面生成。9月19日20时,“桦加沙”加强为强热带风暴。9月20日早晨,“桦加沙”加强为台风。9月20日夜间,“桦加沙”加强为强台风。9月21日8时,“桦加沙”加强为超强台风。截至9月22日5时,其强度已达到17级以上(62米/秒)。9月22日15时,台风“桦加沙”在菲律宾北端的帕努伊坦岛登陆,登陆强度为超强台风级别。
台风“桦加沙”具有强度极端、风圈范围大、来势凶猛等特征,是2025年以来影响中国的最强台风。其将给南海中北部海面、广东省海面及市县带来严重风雨浪潮影响,需提前进行巨灾防御准备,广东省全面进入临战状态。2025年9月22日,台风“桦加沙”袭击菲律宾,山体滑坡致该国1死7伤。
CSP考试后,台风再次肆虐。为了保护大家,M组织的 冲奖1班 战队 派出了一位有抗战台风“山竹”胜利经验的 wxz。wxz 身手不凡,曾在2024深华普及组暑假集训上课时连续吃掉一大袋山竹。所以大家坚信,只要多克隆几个 wxz,再大的台风都不用怕!
题目描述
码力王国可以表示为一个 的网格。台风从左上角 (1,1) 出发,每次只能向右或向下移动一格,最终到达右下角 (n,m)。台风的初始强度为 。wxz 可以在网格的某些格子上放置自己的克隆体。当台风经过一个放置了山竹吃货的格子时,其强度会减少 。如果台风在移动过程中强度降至零或以下,则台风会被消散。
wxz 希望无论台风选择哪条路径,都能在到达 (n,m) 前被消散。请问 wxz 至少需要放置多少个自己的克隆体?如果无法实现,输出 Impossible。
输入格式
第一行包含四个整数 。
输出格式
如果无法实现,输出 Impossible,否则输出一个整数表示最少需要放置的克隆体数量。
样例
2 2 3 2
2
1 1 10 1
Impossible
样例解释
- 对于样例 1,网格大小为 ,路径长度为 。初始强度 ,每个 wxz 减少强度 ,因此需要至少 2 个吃货。
- 对于样例 2,网格大小为 ,路径长度为 。需要减少强度 ,但只有一个格子,无法放置足够吃货,因此输出
Impossible。
数据范围
Tips:年年 桃树下 风来 一个 砸成 俩
统计
相关
在下列比赛中: