P11429 [COCI 2024/2025 #2] 谬误 / Paradoks

题目背景

译自 COCI 2024/2025 #2 T1。$\texttt{1s,0.5G}$。满分为 $50$。

题目描述

五个人围坐在圆桌边上玩游戏。顺时针方向上看过去，五个人分别是 $\text{Igor, Lea, Marino, Sonja, Viktor}$。

游戏有 $n$ 场。第一场第一个出牌的人为 $\text{Sonja}$，此后每一场第一个出牌的人都是上一场的胜者。每场中，五个人按顺时针方向上的顺序依次出牌，每个人恰好出一次牌。

每人手里都有 $n$ 张无色牌，编号 $1\sim n$。出牌时，选择手中的一张牌，并选择红蓝黄绿中的一种颜色涂在牌上打出。此外，我们要求，颜色和数字的组合之前没有被打出过。

每场中，第一个出牌的人打出的牌的颜色称为场风。每个人打的牌的颜色都应该尽可能是场风。如果没有打出场风的牌的话，那么从此刻开始（在接下来的场次中）他就再也不能打（该场次）场风的牌了。

每场中胜者的确定方式如下：

• 如果有人打出过红牌，则取打出数字最大的那个人；
• 否则，取打出牌颜色是场风中数字最大的那个人；

有时候，会有人打出的牌违反规则：牌的颜色与数字组合已经被打出过了，或者使用了被禁用的颜色。此时我们称这次出牌谬误（paradox）。谬误的出牌是无效的，也就是说，出的谬误牌会被忽略掉，不算入胜者的计算，（如果是第一次打出的话）也不算打出过。保证每场第一个人出的牌不会谬误。

给定 $n$ 场中，出的五张牌依次是什么。你需要确定这场中出现了多少个谬误，并输出谬误出现的场次，以及是谁打出了谬误。

输入格式

第一行，一个正整数 $n$。

接下来 $n$ 行，每行五个字符串，每个字符串两个字符，表示这轮依次打出的牌：

• 第一个字符，一个大写英文字母，代表颜色：
  • $\texttt{C}$：红色；
  • $\texttt{P}$：蓝色；
  • $\texttt{Y}$：黄色；
  • $\texttt{Z}$：绿色。
• 第二个字符：数字 $1\sim 9$。

输出格式

第一行，输出悖论数量 $k$。

接下来 $k$ 行，每行先是一个数字，再是一个字符串（全部大写），表示悖论发生的场次，以及谁打出了悖论。按顺序输出。

输入输出样例 #1

输入 #1

4
Y5 Z3 Y6 C2 Y1
Z4 Z7 Z2 Y2 P3
Z6 Z7 Z1 Y2 C2
P6 P8 P8 Z7 Y9

输出 #1

6
2 VIKTOR
3 SONJA
3 LEA
4 VIKTOR
4 IGOR
4 LEA

输入输出样例 #2

输入 #2

3
P1 Y9 Z5 Y1 Z5
P5 Y7 Z3 Y8 P1
C6 Y8 P5 Z1 Z8

输出 #2

4
1 MARINO
2 MARINO
3 VIKTOR
3 IGOR

输入输出样例 #3

输入 #3

1
Y4 P9 Y8 Z5 Z3

输出 #3

0

说明/提示

样例解释

样例 $1$ 解释见图片。

数据范围

对于 $100\%$ 的数据，保证 $1\le n\le 10$。

子任务编号	特殊性质	得分
$1$	AB	$10$
$2$	B
$3$		$30$

• 特殊性质 A：
  • 每场比赛的胜利者都是 $\text{Sonja}$。
• 特殊性质 B：
  • 谬误的原因只有一个：打出了之前打出过的牌。

#5698. 「COCI 2024/2025 #2」Paradoks

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

译自 COCI 2024/2025 Contest #2 T1「Paradoks」

在一个月圆之夜，当时钟敲响午夜时，五个朋友准备好玩一个像那个夜晚一样神秘的游戏。

他们围坐在一张圆桌旁，按顺时针方向依次为：Igor、Lea、Marino、Sonja 和 Viktor。游戏由 $N$ 个回合组成。第一回合由 Sonja 开始，之后每一回合由上一回合的获胜者开始。

每个玩家手中持有 $N$ 张牌。所有的牌都是无色的，且上面有一个 $1$ 到 $9$ 之间的正整数。当玩家出牌时，他们需要为那张牌选择一种颜色。他们可以从四种颜色（红、蓝、黄、绿）中选择一种，前提是该牌（该数字与颜色的组合）尚未在游戏中被出过。在下文中，诸如“出一张蓝色牌”这样的表述，是指执行出牌并将其声明为蓝色的过程。

在每一回合中，玩家按顺时针顺序各出一张牌，直到轮到该回合的起始玩家，即直到每位玩家都出了一张牌为止。回合中打出的第一张牌决定了所谓的回合颜色，后续所有玩家必须打出该颜色的牌。如果任何玩家未能打出当前回合颜色的牌，则视为该玩家手中已无该颜色的牌——他们被禁止在游戏的剩余部分打出该颜色的牌。

每一回合的获胜者判定规则如下：

• 打出红色牌且数字最大的人。
• 如果没有打出红色牌，则打出回合颜色牌且数字最大的人。

有时，玩家会做出不应该做的操作：要么打出一张已经出过的牌，要么打出一张他们之前声明过已不再持有的颜色的牌。这种操作被称为悖论（在克罗地亚语中为：paradoks）。当发生悖论时，该出牌行为在计算回合胜者及游戏的后续过程中被完全忽略。例如，如果某张牌第一次被打出时就构成了悖论，那么在游戏的其余部分中，它将被视为尚未被打出。保证每回合的第一位玩家永远不会在该回合中制造悖论。

我们的英雄们已经很久没有见面了，也没太专心于游戏，所以他们请求你的帮助。请编写一个程序，按照回合顺序列出已打出的牌，统计发生了多少次悖论，并按发生的先后顺序将它们列出。对于每一个悖论，输出它发生的轮次以及制造该悖论的玩家名字。

输入格式

第一行输入包含一个正整数 $N$ $(1 \leq N \leq 10)$，即回合数。

在接下来的 $N$ 行输入中，每行包含 $5$ 个长度为 $2$ 字符的单词，代表该回合中打出的牌，按出牌顺序排列。（注意：每回合的第一位玩家不一定是同一个。）

每个单词的第一个字符代表玩家打出的牌的颜色，为以下字母之一：C（红色）、P（蓝色）、Y（黄色）、Z（绿色）。每个单词的第二个字符为 $1$ 到 $9$（含）之间的正整数，代表牌上的数字。

例如，单词 Y5 表示一张数字为 $5$ 的黄色牌。

输出格式

输出一个数字 $a$，即发生的悖论总数。

在接下来的 $a$ 行中，对于每一个悖论，输出轮次编号和制造该悖论的玩家名字（用大写字母）。

悖论应按发生的先后顺序输出。

样例 1

输入

4
Y5 Z3 Y6 C2 Y1
Z4 Z7 Z2 Y2 P3
Z6 Z7 Z1 Y2 C2
P6 P8 P8 Z7 Y9

输出

6
2 VIKTOR
3 SONJA
3 LEA
4 VIKTOR
4 IGOR
4 LEA

游戏过程如下图所示。

在第 $1$ 轮中，Viktor 和 Lea 没有打出黄色牌（回合颜色），因此假设他们手中已无黄色牌，且在游戏剩余部分被禁止声明任何牌为黄色。这就是 Viktor 在第 $2$ 轮发生悖论以及 Lea 在最后一轮发生悖论的原因。

注意：在第 $2$ 轮中，由于悖论，Viktor 的操作被忽略，我们不再做任何进一步推断。此外，牌 Y2 不被视为已出，这就是为什么 Igor 在第 $3$ 轮打出该牌时没有发生悖论的原因。

第 $3$ 轮和第 $4$ 轮中所有的悖论（除最后一个外）都是因为打出了一张在游戏早期已经出过的牌。

样例 2

输入

3
P1 Y9 Z5 Y1 Z5
P5 Y7 Z3 Y8 P1
C6 Y8 P5 Z1 Z8

输出

4
1 MARINO
2 MARINO
3 VIKTOR
3 IGOR

样例 3

输入

1
Y4 P9 Y8 Z5 Z3

输出

0

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$10$	Sonja 将赢得所有回合，且所有悖论均因重复打出已出过的牌而产生。
$2$	$10$	所有悖论均因重复打出已出过的牌而产生。
$3$	$30$	无附加限制。