题目描述

当抓取流程偏离正常轨道时，机器人需要从当前有限状态中规划一条恢复路径。每个恢复动作有前置条件、状态改写、风险与能量变化，以及时间、能量、风险三部分代价。你需要找到总代价最小的可行恢复序列。

状态为 8 元组：

pos vis path mode grip risk retry energy

目标状态要求 vis=1、path=1、grip=1、risk <= risk_limit 且 energy >= min_energy。每个动作的前置字段为 pre_pos pre_vis pre_path pre_mode pre_grip，值为 -1 表示不限制；还要求当前能量不少于 need_energy。若当前风险大于动作的 max_risk，只有 safe_back=1 的动作仍可执行。若动作会增加重试次数 inc_retry=1，则当前 retry 必须小于 max_retry。

动作产生新状态时，dpos dvis dpath dmode dgrip 中非负值会覆盖对应字段，-1 表示保持；新风险为 max(0, risk + drisk)，新重试次数加上 inc_retry，新能量为 energy - denergy。新状态必须仍满足 energy >= min_energy 且 risk <= risk_limit。

动作代价为 time_cost + alpha * energy_cost + beta * risk_cost。使用该代价进行最短路搜索；若总代价相同，选择动作数更少的方案，再选择动作编号序列字典序更小的方案。

输入格式

第一行输入初始状态 8 个整数：

pos vis path mode grip risk retry energy

第二行输入 risk_limit min_energy max_retry。第三行输入 alpha beta。第四行输入动作数 a。

接下来 a 行，每行输入一个动作：

aid safe_back inc_retry pre_pos pre_vis pre_path pre_mode pre_grip need_energy max_risk dpos dvis dpath dmode dgrip drisk denergy time_cost energy_cost risk_cost

输出格式

若无法恢复到目标状态，输出：

SAFE_STOP

否则输出：

cost len aid1 aid2 ... STATE pos vis path mode grip risk retry energy

cost 保留 6 位小数。

数据范围与测试提示

• 正式测试会覆盖样例没有出现的边界输入，请不要依赖样例规模或样例顺序写特判。
• 输出只包含题目要求的字段，不要输出调试信息；浮点结果按题面要求保留 6 位小数。
• 恢复路径可能不存在，也可能刚好达到代价预算；等号是否可行以题面规则为准。
• 路径搜索需同时维护位置、阶段和资源状态，不能只在位置图上求最短路。
• 起始状态可能已满足恢复目标；动作前置字段 -1 是通配，safe_back=1 只绕过动作自身风险前置限制。

样例

输入样例 1

1 0 0 0 1 3 0 5
5 1 2
1 1
3
1 0 0 -1 0 -1 -1 -1 1 5 -1 1 -1 -1 -1 -2 1 1 1 1
2 0 0 -1 -1 0 -1 -1 1 5 -1 -1 1 -1 -1 0 1 2 1 0
3 0 1 -1 1 1 0 -1 2 5 -1 -1 -1 1 -1 0 1 1 1 0

输出样例 1

6.000000 2 1 2 STATE 1 1 1 0 1 1 0 3

输入样例 2

1 1 1 0 1 1 0 5
5 1 2
1 1
1
1 0 0 -1 -1 -1 -1 -1 1 5 -1 -1 -1 -1 -1 0 1 1 1 1

输出样例 2

0.000000 0  STATE 1 1 1 0 1 1 0 5