本题是2007年度最佳RPG游戏之一——《仙剑奇侠传四》中最后一战的简化版。你的任务和原作一样,是用 4 个主人公打败玄霄(XX)和夙瑶(SY),阻止琼华派飞升。
游戏的主角有 4 个:云天河(YTH),韩菱纱(HLS),柳梦璃(LML)和慕容紫英(MRZY)。战斗开始前,你需要恰好选 3 人上场,并且按照某种顺序排列。令排序后的 3 个主角分别为 H1、H2 和 H3。和游戏中一样,这一战只需打败夙瑶即可。尽管在游戏中,玄霄也是可以打败的,但在本题中,请假设玄霄拥有不死之身。
如上图所示是一张战斗截图,其中 H1 是 YTH,H2 是 HLS,H3 是 LML。战斗采用半回合制,即战斗双方的每个人都有一个头像在“进度条”上从左到右移动,只有当头像移到最右端,则行动的优先级从高到低依次为 YTH、HLS、LML、MRZY、XX 和 SY。当有角色在行动时,所有头像停止移动。至其行动完毕后,该角色的头像重新开始从进度条左端点向右移动。没有角色行动时,所有头像同时向右移动(但速度不一定相同)。
在本题中,每个角色有 4 个基本属性:精、气、神、速。
精:生命力。当精的数值 ≤0 时,该角色死亡。每个角色都有一个精的上限,用 maxjing 表示。
气:用来进行特殊技攻击。当气不够时,某些特殊技无法使用。每个角色的气上线总是 100。
神:用来催动仙术。当神不够时,某些仙术将无法使用。每个角色都有一个神上线,用 maxshen 表示。
速:决定该角色头像在进度条上的移动速度。速总是 1~4 的整数。若一个角色的速 =x,则它的头像恰好需要 5−x 个单位时间从进度条的最左端移到最右端。一个角色的速用 su 表示(在本题中,每个角色的速是不变的)。
为简单起见,本题假设玄霄和夙瑶采用如下的简单攻击策略:
在ta的第 4n+1 次 (n=0,1,2...) 行动中,对 H1 进行武器攻击。
在ta的第 4n+2 次 (n=0,1,2...) 行动中,对 H2 进行武器攻击。
在ta的第 4n+3 次 (n=0,1,2...) 行动中,对 H3 进行武器攻击。
在ta的第 4n+4 次 (n=0,1,2...) 行动中,对 H1、H2、H3 全体进行特殊技攻击。
每个主角都用 4 个属性来描述玄霄和夙瑶对自己的伤害: d1x 和 d2x 表示玄霄的武器攻击和特殊技攻击对自己的伤害,而 d1s 和 d2s 表示夙瑶的武器攻击和特殊技攻击对自己的伤害。
作为一个剧情派玩家,你不想过多的斟酌战斗策略,因此在一名主角需要行动时,你只会考虑以下 4 中可能:
用武器攻击玄霄或夙瑶其中一人。注意,夙瑶已经使用了九幽猝寒剑护体,因此,如果对她进行武器攻击,攻击者将被反弹至伤,因反弹所受的伤害值等于夙瑶遭受的伤害值,用 wad 表示。用武器攻击玄霄(如果你愿意),则不会被反弹。
用仙术“雨润”恢复自己的精。使用一次雨润,将消耗 yurun_shen 个单位的神,增加 yurun_jing 个单位的精(若超过 maxjing 则精将变回 maxjing)
用道具“鼠儿果”恢复自己的神(假设你的鼠儿果有无穷多)。每次只能使用一个鼠儿果,将增加 shuerguo_shen 个单位的神(若超过 maxshen 则神将变回 maxshen)
进行特殊技攻击。每名主角恰好会一种特殊技,同时攻击夙瑶和玄霄。注意:有些特殊技也是物理攻击(这些特殊技用 ssp=1 表示,其它特殊技满足 ssp=0),因此也会被夙瑶反弹至伤,因反弹所受的伤害值等于夙瑶遭受的伤害值,用 ssd 表示。特殊技需要的气用 ssq 表示。
你可能已经注意到,仙术和道具都无法回复气。事实上,只有两种方法可以攒气:使用武器攻击或者被武器攻击打中。使用特殊技攻击、被特殊技打中或被反弹致伤时,气不会增加。每次进行武器攻击时,气将增加 q1;每次被武器攻击打中时,气将增加 q2(如果气超过 100,将变回 100)。
你是一个完美主义者,因此你不希望战斗中有任何一位主角死亡,哪怕是暂时的。特别是打败夙瑶是,不能让主角与她同归于尽。你的任务是精密计划每个角色的每次行动,使得在上述前提之下,用尽可能短的时间(只计算头像移动时间,不算行动时间)打败夙瑶。
输入格式
输入包括不超过 100 组数据,每组数据的第一行为 6 个正整数,分别是 SY_jing,XX_su,SY_su,yurun_jing,yurun_shen,shuerguo_shen。 接下来的 4 行分别是描述 YTH,HLS,LML 和 MRZY 的属性,其中每行包括 16 个非负整数:maxjing,maxshen,su,d1x,d2x,d1s,d2s,wad,ssd,ssq,ssp,q1,q2,jing,qi,shen,最后三个整数表示战斗开始时的精气神值,保证合法。
输入结束标志为 0 0 0 0 0 0
。
输出格式
对于每组数据,输出最短时间和所有可能的角色顺序。每种角色顺序用 3 个字母来表示,其中每个字母代表一个角色(Y-云天河,H-韩菱纱,L-柳梦璃,M-慕容紫英)。比如,若 H1 是韩菱纱,H2 是柳梦璃,H3 是云天河,则角色顺序用 HLY 表示。所有可能的角色顺序按照字典序排列。如果无法在 12 个回合内取胜,输出 −1。
数据范围
翻译来自 刘汝佳,陈锋《算法竞赛入门经典-训练指南》