#P18446. Grand Finale
Grand Finale
Grand Finale
输入:标准输入;输出:标准输出。
在 Pigeland,Slay the Pig 是最受欢迎的 Roguelike 游戏,玩家使用卡牌挑战名为 Evil Potato Lord 的首领。
一般游戏规则如下:
- 玩家开始时有一些初始手牌,以及一个从顶到底排列的抽牌堆。
- 任意时刻,卡牌只可能位于手牌或抽牌堆中。
- 玩家可以打出手牌中的牌;每次打出时,先弃掉这张被打出的牌,再结算它的效果。
- 只有当前这张牌的所有效果都结算完毕后,才能打出下一张牌。
本题只考虑抽牌效果,抽牌规则如下:
- 打出能抽牌的卡牌后,按照牌堆从顶到底的顺序,逐张尝试把指定数量的牌抽入手牌。
- 手牌数量上限为 ,任意时刻都不能超过 。
- 如果尝试抽取牌堆顶的牌时,手牌已有 张,那么这张被抽到的牌直接从牌堆中弃掉,不进入手牌,也不触发任何效果。
- 如果抽牌堆已经为空,那么这一次抽牌不产生任何效果。
以 Grand Finale 为核心的牌组十分强大,打出这张牌会对所有敌人造成大量伤害,通常能带来胜利。但它有一个严格的出牌条件:抽牌堆必须为空。
Bie-Bot 的牌组只含以下四类卡牌:
| 字符 | 卡牌 | 本题中的效果或条件 |
|---|---|---|
G |
Grand Finale | 仅当抽牌堆为空时才能打出;整个牌组中恰好有一张 |
Q |
Quick Slash | 抽一张牌 |
B |
Backflip | 按顺序抽两张牌 |
W |
Wound | 一旦进入手牌,就不能被打出 |
原题四种牌的示意图如下。本题采用上述简化规则,仅考虑抽牌,不引入图片中的伤害、格挡或费用机制。

Bie-Bot 幸运地在初始手牌中抽到了唯一的 G,并且知道整个抽牌堆从顶到底的顺序。他希望最终能打出 G。
给定长度为 的字符串 表示初始手牌,长度为 的字符串 表示牌堆从顶到底的顺序。 由 GQBW 构成且恰有一个 G; 仅由 QBW 构成。可以在任意时刻选择手中可打出的牌,按最优策略行动。
求能够成功的最小手牌上限 ,要求 。如果不存在这样的上限,则报告无法成功。
输入格式
第一行包含整数 ,表示测试用例数。
对于每个测试用例:
第一行包含两个整数 ()。
第二行包含长度为 的字符串 ,仅含大写字母 G、Q、B、W,且恰好含有一个 G。
第三行包含长度为 的字符串 ,仅含大写字母 Q、B、W。
保证一个输入文件内,所有测试用例的 之和不超过 。
输出格式
对每个测试用例输出一行:
- 如果可以成功,输出能够最终打出 Grand Finale 的最小整数手牌上限 ,其中 。
- 否则输出
IMPOSSIBLE。
原样例
2
2 6
BG
BQWBWW
4 6
GQBW
WWWWQB
3
IMPOSSIBLE
原样例说明
用“手牌/抽牌堆”的形式表示当前局面。第一个测试用例在 时,一种最优策略如下;手牌中的书写顺序不影响出牌选择。
BG/BQWBWW,打出B,得到BQG/WBWW。BQG/WBWW,打出Q,得到BWG/BWW。BWG/BWW,打出B,得到BWG/W。这里由于手牌已满,丢弃了一张抽到的W。BWG/W,打出B,得到WWG/∅。由于牌堆只剩一张,此次实际只抽到一张。WWG/∅,打出G,成功。