TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

100.0% (44/44)

Submission's AC Ratio

60.8% (62/102)

Tags

Description

Hangman 是一種經典的猜字遊戲,通常兩個或以上玩家一起玩。遊戲的主要目的是猜出一個單詞中的所有字母,通常在有限的錯誤次數內,避免「被吊死」的懲罰圖像被完整畫出。這是一個結合猜測、語言和邏輯的遊戲。 - 人工智障

施~~竣~~耀~~ 覺得原版的 Hangman 規則太無聊了,所以他研發了改良過後的雙人版 Hangman,遊戲規則如下:

  1. 遊戲中有兩名玩家 A 跟 B,雙方會各自選擇一個由小寫字母組成的字串作為自己的秘密字串。
  2. 每一回合都由 A 開始:他每次會猜測一個字母。如果 B 的秘密字串中包含此字母,B 需要將該字母填入他的秘密字串中。(所有該字母出現的位置都會被填入)
  3. 接下來則輪到 B 猜測 A 的秘密字串的字母。
  4. 雙方都猜了一個字母過後一回合結束。如果此時只有一方的秘密字串被全部猜中,則另一方獲勝;如果雙方的秘密字串皆被全部猜中,則遊戲結果為平手;如果雙方的秘密字串都有字母還沒被猜中,則繼續下一回合,一直到遊戲結束為止。

假設 A 的秘密字串是 bob,B 的秘密字串是 banana ,那遊戲可能會這樣子進行:

  • 第一回合中,A 猜了字母 a,猜中了三個位置,使得 B 的字串變成 _a_a_a;B 猜了字母 p,沒有猜中。
  • 第二回合中,A 猜了字母 n,使得 B 的字串變成了 _anana;B 猜了字母 o,使得 A 的字串變成了 _o_
  • 第三回合中,A 猜了字母 b,使得 B 的字串變成了 banana;B 猜了字母 x,沒有猜中。
  • 由於 B 的秘密字串已被全部猜中,這次遊戲由 A 獲勝。

值得注意的是,如果 B 在第三回合中猜的字母是 b,則會因為雙方的秘密字串都被全部猜中了,導致遊戲變成平手。

你決定跟人工智障比賽,其中你當作 A 玩家,人工智障當作 B 玩家。但是經過一段時間後,你發現人工智障真的是名不虛傳的人工智障:每一回合中,人工智障猜的字母都會跟你猜的字母一樣。你想寫一個程式判斷,在給定你的秘密字串跟人工智障的秘密字串的情況下,你有沒有機會贏得這次比賽。

Input Format

第一行會有兩個整數 $n$, $m$,代表你的秘密字串長度跟人工智障的秘密字串長度
第二行會有一個字串 $A$,代表你的秘密字串
第三行會有一個字串 $B$,代表人工智障的秘密字串

對於所有測試資料:

  • $1 \leq n, m \leq 10 ^ 5$
  • $A, B$ 由小寫字母組成
  • $n = |A|, m = |B|$

Output Format

如果有可能贏過人工智障,請輸出Yes;如果無論如何都無法贏過人工智障,請輸出No

Sample Input 1

1 1
a
a

Sample Output 1

No

Sample Input 2

3 2
abc
bc

Sample Output 2

Yes

Sample Input 3

2 3
bc
abc

Sample Output 3

No

Sample Input 4

14 7
ecclesiastical
phoenix

Sample Output 4

Yes

Hints

範例測資 1 解釋:只要你猜了字母 a,人工智障也會立馬猜字母 a,導致遊戲無論如何都是平手,因此請輸出 No

範例測資 2 解釋:如果你在第一回合猜了字母 b,第二回合猜了字母 c,則在兩回合後,你的秘密字串會變成 _bc,還沒被全部猜完;但人工智障的秘密字串已被全部猜中,因此你有可能獲勝,請輸出 Yes

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~3 範例測資 0
2 0, 4~8 $A=B$ 38
3 0~2, 9~17 $n, m \leq 100$,$A,B$ 由 a-h 的小寫字母組成 21
4 0~29 無其他限制 41

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1 2 3 4
1 1000 65536 65536 1 3 4
2 1000 65536 65536 1 3 4
3 1000 65536 65536 1 4
4 1000 65536 65536 2 4
5 1000 65536 65536 2 4
6 1000 65536 65536 2 4
7 1000 65536 65536 2 4
8 1000 65536 65536 2 4
9 1000 65536 65536 3 4
10 1000 65536 65536 3 4
11 1000 65536 65536 3 4
12 1000 65536 65536 3 4
13 1000 65536 65536 3 4
14 1000 65536 65536 3 4
15 1000 65536 65536 3 4
16 1000 65536 65536 3 4
17 1000 65536 65536 3 4
18 1000 65536 65536 4
19 1000 65536 65536 4
20 1000 65536 65536 4
21 1000 65536 65536 4
22 1000 65536 65536 4
23 1000 65536 65536 4
24 1000 65536 65536 4
25 1000 65536 65536 4
26 1000 65536 65536 4
27 1000 65536 65536 4
28 1000 65536 65536 4
29 1000 65536 65536 4