AT_abc166_f [ABC166F] Three Variables Game

题目描述

在某个游戏中，有三个变量，分别用 $A$、$B$、$C$ 表示。

随着游戏的进行，你需要进行 $N$ 次选择。每一次选择由字符串 $s_i$ 表示，当 $s_i$ 为 AB 时，表示你可以选择给 $A$ 或 $B$ 加 $1$，同时从另一个变量减去 $1$；当 $s_i$ 为 AC 时，表示你可以选择给 $A$ 或 $C$ 加 $1$，同时从另一个变量减去 $1$；当 $s_i$ 为 BC 时，表示你可以选择给 $B$ 或 $C$ 加 $1$，同时从另一个变量减去 $1$。

在每一次选择之后，$A$、$B$、$C$ 的值都不能为负数。

请判断是否存在一种选择方式，使得能够完成全部 $N$ 次选择且始终满足上述条件。如果存在，请给出一种可行的选择方案。

输入格式

输入以如下格式从标准输入读入：

$N$ $A$ $B$ $C$
$s_1$
$s_2$
$\vdots$
$s_N$

输出格式

如果存在一种选择方式能够完成全部 $N$ 次选择且始终满足条件，则输出 Yes，否则输出 No。

如果输出 Yes，则在接下来的 $N$ 行中，依次输出每次选择中被加 $1$ 的变量名（A、B 或 C）。

输入输出样例 #1

输入 #1

2 1 3 0
AB
AC

输出 #1

Yes
A
C

输入输出样例 #2

输入 #2

3 1 0 0
AB
BC
AB

输出 #2

No

输入输出样例 #3

输入 #3

1 0 9 0
AC

输出 #3

No

输入输出样例 #4

输入 #4

8 6 9 1
AC
BC
AB
BC
AC
BC
AB
AB

输出 #4

Yes
C
B
B
C
C
B
A
A

说明/提示

限制条件

• $1 \leq N \leq 10^5$
• $0 \leq A,B,C \leq 10^9$
• $N$、$A$、$B$、$C$ 均为整数
• $s_i$ 仅为 AB、AC、BC 之一

样例解释 1

可以如下完成全部 $2$ 次选择：

• 第 $1$ 次选择时，给 $A$ 加 $1$，从 $B$ 减 $1$。此时 $A$ 变为 $2$，$B$ 变为 $2$。
• 第 $2$ 次选择时，给 $C$ 加 $1$，从 $A$ 减 $1$。此时 $C$ 变为 $1$，$A$ 变为 $1$。

由 ChatGPT 4.1 翻译