金铲铲模拟器

题目描述:

你正在进行一场《金铲铲》的对局。

游戏中共有 $m$ 种不同的弈子，每种弈子都有自己的费用和羁绊。你需要管理金币、等级、场上弈子以及备战席，并根据每回合出现的商店完成整场游戏。

本题中的所有行为均由游戏规则决定，不需要进行策略选择。

请你模拟 $n$ 个回合后，输出游戏结束时的状态。

弈子

共有 $m$ 种弈子，编号为 $1\sim m$。

第 $i$ 种弈子具有：

• 购买费用 $c_i$；
• $k_i$ 个羁绊。

每个羁绊由一个字符串表示。

玩家对同一种弈子的持有数量最多为 $3$。

当持有某种弈子的数量达到 $3$ 时，这三张弈子立即合成为一张二星弈子。

一星弈子的星级为 $1$，合成后的弈子的星级为 $2$。

同一种编号的弈子不能同时存在于场上。

等级与金币

游戏开始时，等级为 $1$，拥有 $G$ 枚金币。

当玩家处于等级 $i$ 时，升级到等级 $i+1$ 需要花费 $up_i$ 枚金币，最高等级为 $LC$。

每个回合开始时，会获得一笔利息和额外金币。

若当前金币为 $G$，本回合额外获得 $x$ 枚金币，则获得金币后：

$$
G\leftarrow G+\min(5,\lfloor G/10\rfloor)+x
$$

随后，如果当前等级尚未达到 $LC$ 且金币不少于当前等级的升级费用，则立即升级一次，并支付相应费用。

场上与备战席

当前等级为 $level$ 时，场上最多可以存在 $level$ 名不同编号的弈子。

备战席最多可以存放 $k$ 张弈子。

备战席按照弈子进入的先后顺序排列。

新获得的弈子进入备战席末尾。

当需要从备战席中选择弈子时，总是优先检查位于最前面的弈子。

若该弈子当前不满足本次操作的要求，则将它重新放到备战席末尾，再继续检查下一张。

羁绊

对于每种羁绊，记录当前场上拥有该羁绊的弈子数量。

只要某个羁绊当前有至少一名场上弈子拥有，就认为该羁绊存在。

当一名弈子进入场上时，它所拥有的每一种羁绊数量均增加 $1$。

初始状态

游戏开始时：

• 等级为 $1$；
• 拥有 $G$ 枚金币；
• 编号为 $t$ 的一星弈子位于场上；
• 备战席为空。

弈子 $t$ 所拥有的所有羁绊均计入场上羁绊。

每回合流程

每回合会依次进行以下事件：

1. 获得金币；
2. 判断是否升级；
3. 若本回合升级，则进行一次特殊的上场操作；
4. 依次处理商店中的 $5$ 张弈子；
5. 回合结束时进行场上补位。

升级后的上场

若本回合成功升级，则升级完成后立即进行一次上场操作。

此时，从备战席当前的排列顺序开始检查。

对于一张弈子：

• 如果该编号的弈子已经在场上，则将它重新放到备战席末尾；
• 否则，如果它至少拥有一个当前已经存在的羁绊，则令它进入场上；
• 如果它既未在场上，又没有与当前场上羁绊产生联系，则将它重新放到备战席末尾。

一旦有弈子成功进入场上，本次操作立即结束。

本次操作至多使一名弈子进入场上。

商店

每回合商店会按照从左到右的顺序出现 $5$ 张弈子牌。

同一种弈子可以在同一回合的不同位置重复出现。

设当前商店中的弈子编号为 $id$。

当满足以下任意条件时，不会购买这张牌：

$$
G<c_{id}
$$

或

$$
这张牌已经升至二星
$$

 

对于能够购买的弈子，只要满足以下任意条件，就会购买：

• 该弈子拥有至少一个当前已经存在的羁绊；
• $c_{id}>3$。

否则不购买。

购买与合成

当决定购买某张弈子时，只有在以下条件至少满足一个时，购买才会成功：

$$
|备战席|<k
$$

或

$$
count_{id}=2， 其中 count_{id} 表示当前持有的弈子 id 的数量。
$$

购买成功后，支付对应费用，并使该弈子的持有数量增加 $1$。

若购买后持有数量仍小于 $3$，则将一张一星弈子加入备战席末尾。

若购买后恰好达到 $3$ 张，则立即完成合成。

合成时，备战席中所有编号为 $id$ 的弈子都会被移除。

若编号 $id$ 的弈子已经在场上，则直接将场上的它变为二星。

否则，将一张二星弈子加入备战席末尾。

回合结束时的补位

商店处理完成后，如果场上弈子数量少于当前等级，则进行补位。

补位时不考虑羁绊。

不断从备战席最前面检查弈子：

• 如果该编号已经在场上，则将这张弈子重新放到备战席末尾；
• 否则，这张弈子进入场上。

弈子进入场上后，其所有羁绊的数量各增加 $1$。

当上场一张奕子，或者备战席中已经没有可以处理的弈子时，本次补位结束。

输入格式:

第一行包含五个整数：

$$
n\quad m\quad k\quad G\quad LC
$$

分别表示：

• $n$：游戏回合数；
• $m$：弈子种类数；
• $k$：备战席容量；
•  $G$：初始金币；
• $LC$：等级上限。

第二行包含 $LC$ 个整数：

$$
up_1,up_2,\ldots,up_{LC}
$$

其中 $up_i$ 表示从等级 $i$ 升到等级 $i+1$ 所需的金币。

接下来 $m$ 行，每行描述一种弈子。

第 $i$ 行包含：

$c_i \ k_i \ name_1 \ name_2 \ ... \ name_{k_i} $

其中：

• $c_i$ 表示弈子 $i$ 的费用；
• $k_i$ 表示弈子 $i$ 拥有的羁绊数量；
• $ name_1 ... name_{k_i}$ 表示它拥有的羁绊。

接下来一行包含一个整数：

$t$

表示初始位于场上的弈子编号。

接下来 $n$ 行描述每个回合。

每行包含：

$x\ a_1\ a_2\ a_3\ a_4\ a_5$

其中：

• $x$ 表示本回合额外获得的金币；
• $a_1,a_2,a_3,a_4,a_5$ 表示商店从左到右出现的 $5$ 张弈子牌。

输出格式:

第一行输出两个整数：

$level G$

分别表示游戏结束时的等级和金币。

接下来输出当前场上存在的所有羁绊。

每行输出：

$name count$

按照羁绊名称的字典序输出。

随后输出当前位于场上的所有弈子。

每行输出：

$id star$

其中 `star` 表示星级。

场上弈子按照编号从小到大输出。

最后输出备战席中的所有弈子。

每行输出：

$id star$

按照备战席当前从前到后的顺序输出。

若某一部分为空，则不输出任何内容。

数据范围:

对于所有测试数据：

$$
1\le n\le2\times10^5
$$

$$
1\le m\le2\times10^5
$$

$$
1\le k\le2\times10^5
$$

$$
1\le LC\le8
$$

$$
0\le G\le10^{18}
$$

$$
1\le up_i\le10^{18}
$$

$$
1\le c_i\le5
$$

$$
1\le k_i\le5
$$

每个羁绊名称长度不超过 $20$，仅包含大小写英文字母和数字。

保证所有弈子编号均在 $1\sim m$ 范围内。

样例输入:

(双击复制)

3 4 2 10 3
8 10 20
1 1 Warrior
2 1 Mage
3 2 Warrior Mage
5 1 Assassin
1
2 3 2 4 1 3
0 4 4 2 1 1
3 3 4 2 4 1

样例输出:

(双击复制)

2 0
Mage 1
Warrior 2
1 2
3 1
3 1

时间限制: 1000ms
空间限制: 256MB

---

来源: 温州市计算机学会