#H1051. 模拟还是简单一点好

模拟还是简单一点好

题目背景

今天 Macesuted 、 Tobiichi_Origami 和 jdsb 正在 想象里 打扑克,这个时候 Tobiichi_Origami 灵机一动,就出现了这道题。

三人讨论后,得到了一种有趣的扑克牌玩法,美其名曰“MTJ”。

游戏背景

MTJ 是一种多人牌类回合制游戏,所有玩家在开局时均平等,玩家编号为 11 ~ nn

游戏过程

游戏开始时,每名玩家会从牌堆里抽出 55 张牌。

抽牌方法:以 1,2,3,4n1,n1,2,3,4\dots n-1,n 的顺序(下面提到的所有“顺序”均指此顺序),每名玩家先抽取第一张牌,再以相同的方法抽取第二张牌……直到所有人手上均有 55 张牌。

开始游戏时,所有玩家按顺序依次行动。

每个玩家自己的行动可以分为两个阶段:

  • 出牌阶段: 你可以打出一组牌,出牌策略在下面会给出。
  • 摸牌阶段: 从牌堆顶部拿取若干张牌,直至牌堆为空或你手上的牌数达到你的手牌数量上限。

注意若牌堆为空,你将不能继续摸牌,即使现在你的手牌数量没有达到你的手牌数量上限。

扑克牌

为了简化这道题,MTJ 中的扑克牌没有花色,且扑克牌的点数仅为 [1,k][1,k] 之间的整数。

下面是 MTJ 中将会出现的出牌方法:

  • 连牌: nn 张点数相同的扑克牌(n1n\ge 1
  • 顺子: nn 张点数连续的扑克牌(n3n\ge 3

特别的,MTJ 的顺子可以越过边界,比如当 k=10k=10 时,手牌 6 7 8 9 10 1 2 3 是一个顺子。

甚至下面这个例子也是顺子: 4 5 6 1 2 3 4 5 6 1 2 3k=6k=6

好感度

由于 Tobiichi_Origami 非常喜欢看别人打 MTJ,他对每种牌有不一样的好感度,记他对牌 ii 的好感度为 likeilike_i,注意 likeilike_i 可能为负数。

当玩家打出一个 nn 张牌的连牌时,他将收获 n×likein\times like_i 的好感度。

当玩家打出一个 nn 张牌的顺子时,他将收获 i=1nlikeshuni\sum_{i=1}^{n}like_{shun_i} 的好感度,其中 shunishun_i 表示顺子中的第 ii 张牌。

由于 Tobiichi_Origami 是神,他可以对游戏做出一些更改,当一个玩家的好感度达到 limlim 时,玩家的手牌数量上限将会增加 11,即此时他的手牌数量上限达到 66 张;当该玩家的好感度达到 2×lim2\times lim 时,玩家的手牌数量上限将会再增加 11……以此类推。

同时,如果该玩家的好感度从 limlim 以上下降到 limlim 以下,他的手牌数量上限将会减少 11……。

简单的说:当玩家的好感度为 valuevaluevalue0value\ge 0) 时,他此时的手牌数量上限为 max(value,0)lim+5\bigg\lfloor\dfrac{\max(value,0)}{lim}\bigg\rfloor+5

行动准则

所有玩家均拥有相同的行动准则。

在游戏开始时 11 号玩家拥有主动权。

主动

当玩家掌握主动权时,将会按照下面的准则出牌:

  • 若有顺子,则必出顺子。若有多种顺子出法,则优先出牌数尽可能多的。若有多种出牌数相同的顺子,则优先出第一张牌更大的,
  • 若没有顺子,则出连牌。若有多组连牌,则优先出牌数尽可能多的。若有多组牌数相同的连牌,则优先出扑克牌点数更大的。

掌握主动权的玩家在结束上述操作之后,将会失去主动权。

被动

当玩家没有掌握主动权时,将会按照下面的准则出牌:

  • 若上一次出牌的玩家是玩家本身,玩家得到主动权,使用上文“主动”板块准则出牌。
  • 根据上一次出牌的玩家出的牌,尝试接牌。若能接牌,则必接;若不能,则玩家跳过此回合。

接牌

在玩家处于被动状态时,可能会需要接牌,玩家需要按照下面的准则接牌:

  • 若上一位玩家出的是 nnii 的连牌,玩家必须要: 出 nni+1i+1 以接牌(1i<k1\le i< k);出 nn11 以接牌(i=ki=k)。
  • 若上一位玩家出的是 nn 张顺子,假设顺子的第一张牌为 ii,玩家必须要: 出 nn 张从 i+1i+1 开始的顺子(关于 i=ki=k 的情况同上)

游戏结束

当任意一名玩家打完了所有的手牌并且牌堆为空,该玩家即胜利。

输入格式

第一行三个整数 nnmmkklimlim,分别表示玩家数量、牌堆牌数、扑克牌点数范围和好感度参数。
第二行 kk 个整数 likeilike_i,表示 Tobiichi_Origami 对不同扑克牌的好感度。
第三行 mm 个整数 cardicard_i,表示牌堆从下往上的牌点数。

输出格式

首先你需要输出游戏结束前所有玩家的出牌情况。你需要将他们打出的手牌全部输出,如果是顺子,你需要按照顺序。具体格式见样例。
在游戏结束后,你需要先输出一行 xxx is winner!,其中 xxx 为赢的玩家的编号。
接着你要输出 nn 行,每行格式形如 x:(y) c1 c2 c3 ... cyx 为玩家编号,y 为玩家手牌数量,c1 ~ cy 为玩家的所有手牌。你应该将手牌从小到大输出,详见样例。
最后,你需要输出一行 nn 个整数,表示每名玩家在游戏结束时的喜爱值。
注意: 这里的手牌指游戏结束那一瞬间所有玩家的手牌情况。

3 30 6 5
0 0 0 0 0 0
1 5 2 3 6 1 5 2 3 6 2 2 3 3 1 5 2 4 2 6 1 2 4 2 1 3 4 2 5 1
1:4 4 
1:1 2 3 
2:2 3 4 
2:6 6 
1:1 1 
3:2 2 
1:3 3 
1:6 1 2 
2:1 2 3 
2:5 5 
2 is winner!
1:(1) 2 
2:(0) 
3:(5) 1 2 2 5 5 
0 0 0 

数据规模与约定

Subtask 1(10 pts): n=2\texttt{Subtask 1(10 pts): }n=2m=10m=10k=5k=5
Subtask 2(20 pts): 1ik\texttt{Subtask 2(20 pts): }\forall 1\le i\le klikei=0like_i=0
Subtask 3(20 pts): m=5×n\texttt{Subtask 3(20 pts): }m=5\times n
Subtask 4(50 pts): \texttt{Subtask 4(50 pts): }无特殊条件。

对于 100%100\% 的数据,1<n1001 < n \le 1005×nm1055\times n\le m\le 10^51k101 \le k \le 10likei10|like_i|\le 1040<lim10440 < lim \le 10^4


数据极弱勿喷。