← 返回题目列表

AtCoder · jag2017autumn_b

B. 锦标赛图表

中文机器翻译题面 查看原题

问题陈述

21XX年,一年一度的编程大赛,日本算法大奖赛(JAG)已成为最受欢迎的智力运动赛事之一。

JAG 采用淘汰赛形式进行。今年,$N$ 选手将参加 JAG 比赛。锦标赛图表表示为字符串。 [[a-b]-[c-d]] 是一个简单的例子。本例中,有 4 名参赛者,分别为 a、b、c、d,所有比赛描述如下:

  • 匹配 1 是 a 和 b 之间的匹配。
  • 比赛 2 是 c 和 d 之间的比赛。
  • 第 3 场比赛是 [第 1 场比赛的获胜者] 和 [第 2 场比赛的获胜者] 之间的比赛。

更准确地说,锦标赛图表满足以下 BNF:

  • <获胜者> ::= <人> | “[”<获胜者>“-”<获胜者>“]”
  • <人> ::= "a" | “b”| “c”| ... | “z”

您,JAG 主席,计划公布今年 JAG 比赛的结果。然而,你犯了一个错误,输掉了所有比赛的结果。幸运的是,您找到了锦标赛所有比赛之前打印的锦标赛图表。当然,它根本不包含结果。因此,您向每位参赛者询问了比赛中的获胜次数,并得到了$N$条信息,形式为“参赛者$a_i$赢得了$v_i$次”。

现在,您的工作是确定所有这些回复是否都是真实的。


输入

输入由以下格式的单个测试用例组成。

$S$ $a_1$ $v_1$ $\vdots$ $a_N$ $v_N$

$S$ 代表锦标赛排行榜。 $S$满足上述BNF。 接下来的$N$行代表获胜次数的信息。第 $(i+1)$ 行由小写字母 $a_i$ 和非负整数 $v_i$ ($ v_i \le 26)$ 组成,中间用空格分隔,这意味着参赛者 $a_i$ 赢得了 $v_i$ 次。 注意,$N$ ($2 \le N \le 26$) 表示参赛者的数量,可以通过字符串 $S$ 来识别。您可以假设每个字母 $a_i$ 都是不同的。 保证 $S$ 只包含每个 $a_i$ 一次并且不包含任何其他小写字母。 如果回复对锦标赛图表均有效,则将

输出

打印 您选择的 Yes 写在一行中。 否则,打印 No 一行。


示例输入 1

[[m-y]-[a-o]]
o 0
a 1
y 2
m 0

样本输入 1 的输出

Yes

示例输入 2

[[r-i]-[m-e]]
e 0
r 1
i 1
m 2

样本输入 2 的输出

No