UVA12233 Final Combat

本题是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 个基本属性：精、气、神、速。 - 精：生命力。当精的数值 $\leq 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$。 **数据范围**  **翻译来自 刘汝佳，陈锋《算法竞赛入门经典-训练指南》** [problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=244&page=show_problem&problem=3385 [PDF](https://uva.onlinejudge.org/external/122/p12233.pdf) 

N/A

N/A