← 返回题目列表

AtCoder · iroha2019_day4_c

C. 给你的力量

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

配点 : 500 点

故事

我到达车站时看到的,是正在与异形战斗的伊吕波酱。她像是在舞蹈一样四处移动,戏耍着敌人。

尽管如此,异形的势头依然没有减弱。敌人太多了。我光看着是不行的。依靠你的力量!

問題文

现在,敌人 M 在身体上, i 第N个敌人最初在离你所在位置只有 x_i+0.5 的地方,1 每秒钟 1 都会靠近你。与敌人的距离变为 0 时你将会死亡。严格来说,当距离更近到 0.5 的敌人靠近时,你将会死亡。
另外,每个敌人都有0和1组成的特有字符串, i 第N个敌人拥有的字符串是 s_i。

你持有武器,并且武器也持有0和1组成的字符串 给出为 S。你可以使用该武器进行以下 2 个操作。

  • 击败离你最近的敌人。但前提是,敌人持有的字符串必须在字典顺序上小于你武器持有的字符串。
  • 1 用几秒钟的时间对武器施魔法,改变字符串。

但是,攻击所需的时间非常小,可以忽略不计。另外,在任何行动中,你都不会离开最初所在的位置。

你可以使用的魔法会将你武器持有的字符串按如下方式改变。

  • 在字符串的开头0是 2 添加几个字符。
  • 如果每个字符下方左右邻位的数字相同0,则不同则1写下。但是,如果右边或左边的任意一个字符不存在,则什么也不写。
  • 将下面写下的字符串作为新字符串。

例如,当你的武器有字符串1101时使用魔法,新字符串如下所示1110。

M 身体敌人的情报,以及你武器最初持有的字符串 S 被提供,所以请急救以确定你是否能够安全生存。

制約

  • 0 \leq M \leq 10^5
  • 0 < x_1 \leq x_2 \leq \dots \leq x_M \leq 10^{18}
  • 1 \leq |s_i| (i=1,2,\dots,M)
  • \displaystyle\sum_{i=1}^M |s_i| \leq 10^5
  • 1 \leq |S| \leq 10^5
  • s_i 以及 S 是全部0或 替换为1组成的字符串 给出为

入力

输入是按以下格式从标准输入给出的。

S
M
x_1 s_1
x_2 s_2
:
x_M s_M

出力

击败所有敌人,如果距离 0 之前能够击倒的话 Yes ,如果不能的话 No 请输出。


入力例 1

1101
2
1 1001
2 1101

出力例 1

Yes

可以按照以下方法击败所有敌人。

  • 击倒最近的敌人。
  • 1 秒给武器施加魔法。武器所持有的字符串为1110。敌人 1 接近。
  • 击倒最近的敌人。

入力例 2

1101
2
1 1001
2 1110

出力例 2

No

打败敌人时,武器所持有的字符串必须在字典顺序上更大。


入力例 3

1111
4
1 1
2 011
3 1100
7 0000001

出力例 3

Yes

1 有时候即使不使用魔法也能击败所有的敌人。


入力例 4

00000000
1
1000000000000000000 1

出力例 4

No

也有使用再多魔法也无法击败的敌人。


入力例 5

0110011000
10
1 100
2 0111
3 0000
5 1
5 0
6 0000001
7 11
7 00
8 00
9 0101

出力例 5

No

解説

解説