A. Bark to Unlock

Codeforces

IDCF868A

Time2000ms

Memory256MB

Difficulty—

brute forceimplementationstrings

English · Original

Chinese · Translation

Formal · Original

As technologies develop, manufacturers are making the process of unlocking a phone as user-friendly as possible. To unlock its new phone, Arkady's pet dog Mu-mu has to bark the password once. The phone represents a password as a string of two lowercase English letters. Mu-mu's enemy Kashtanka wants to unlock Mu-mu's phone to steal some sensible information, but it can only bark _n_ distinct words, each of which can be represented as a string of two lowercase English letters. Kashtanka wants to bark several words (not necessarily distinct) one after another to pronounce a string containing the password as a substring. Tell if it's possible to unlock the phone in this way, or not. ## Input The first line contains two lowercase English letters — the password on the phone. The second line contains single integer _n_ (1 ≤ _n_ ≤ 100) — the number of words Kashtanka knows. The next _n_ lines contain two lowercase English letters each, representing the words Kashtanka knows. The words are guaranteed to be distinct. ## Output Print "_YES_" if Kashtanka can bark several words in a line forming a string containing the password, and "_NO_" otherwise. You can print each letter in arbitrary case (upper or lower). [samples] ## Note In the first example the password is "_ya_", and Kashtanka can bark "_oy_" and then "_ah_", and then "_ha_" to form the string "_oyahha_" which contains the password. So, the answer is "_YES_". In the second example Kashtanka can't produce a string containing password as a substring. Note that it can bark "_ht_" and then "_tp_" producing "_http_", but it doesn't contain the password "_hp_" as a substring. In the third example the string "_hahahaha_" contains "_ah_" as a substring.

随着技术的发展，制造商正在使解锁手机的过程尽可能用户友好。为了解锁其新手机，Arkady 的宠物狗 Mu-mu 只需叫出一次密码即可。手机将密码表示为一个由两个小写英文字母组成的字符串。 Mu-mu 的敌人 Kashtanka 想要解锁 Mu-mu 的手机以窃取一些敏感信息，但它只能叫出 #cf_span[n] 个不同的单词，每个单词均由两个小写英文字母组成。Kashtanka 想要连续叫出若干个单词（不一定互不相同），以形成一个包含密码作为子串的字符串。请判断是否可以通过这种方式解锁手机。第一行包含两个小写英文字母 —— 手机上的密码。第二行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 100]) —— Kashtanka 知道的单词数量。接下来的 #cf_span[n] 行，每行包含两个小写英文字母，表示 Kashtanka 知道的单词。这些单词保证互不相同。如果 Kashtanka 能通过连续叫出若干个单词形成一个包含密码作为子串的字符串，则输出 "_YES_"；否则输出 "_NO_"。你可以以任意大小写形式输出每个字母。在第一个例子中，密码是 "_ya_"，Kashtanka 可以依次叫出 "_oy_"、"_ah_" 和 "_ha_"，形成字符串 "_oyahha_"，其中包含密码。因此答案是 "_YES_"。在第二个例子中，Kashtanka 无法生成包含密码的字符串。注意，它可以叫出 "_ht_" 然后 "_tp_" 形成 "_http_"，但该字符串并不包含密码 "_hp_" 作为子串。在第三个例子中，字符串 "_hahahaha_" 包含 "_ah_" 作为子串。 ## Input 第一行包含两个小写英文字母 —— 手机上的密码。第二行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 100]) —— Kashtanka 知道的单词数量。接下来的 #cf_span[n] 行，每行包含两个小写英文字母，表示 Kashtanka 知道的单词。这些单词保证互不相同。 ## Output 如果 Kashtanka 能通过连续叫出若干个单词形成一个包含密码作为子串的字符串，则输出 "_YES_"；否则输出 "_NO_"。你可以以任意大小写形式输出每个字母。 [samples] ## Note 在第一个例子中，密码是 "_ya_"，Kashtanka 可以依次叫出 "_oy_"、"_ah_" 和 "_ha_"，形成字符串 "_oyahha_"，其中包含密码。因此答案是 "_YES_"。在第二个例子中，Kashtanka 无法生成包含密码的字符串。注意，它可以叫出 "_ht_" 然后 "_tp_" 形成 "_http_"，但该字符串并不包含密码 "_hp_" 作为子串。在第三个例子中，字符串 "_hahahaha_" 包含 "_ah_" 作为子串。

**Definitions** Let $ p = p_1 p_2 \in \{a,\dots,z\}^2 $ be the password. Let $ W = \{w_1, w_2, \dots, w_n\} $ be a set of $ n $ distinct words, where each $ w_i = w_{i,1} w_{i,2} \in \{a,\dots,z\}^2 $. **Constraints** $ 1 \le n \le 100 $ **Objective** Determine whether there exists a finite sequence $ w_{i_1}, w_{i_2}, \dots, w_{i_k} \in W $ (with repetition allowed) such that the concatenated string $ w_{i_1} w_{i_2} \cdots w_{i_k} $ contains $ p $ as a contiguous substring. Output "YES" if such a sequence exists, "NO" otherwise.

Samples

Input #1

ya
4
ah
oy
to
ha

Output #1

YES

Input #2

hp
2
ht
tp

Output #2

NO

Input #3

ah
1
ha

Output #3

YES

API Response (JSON)

{
  "problem": {
    "name": "A. Bark to Unlock",
    "description": {
      "content": "As technologies develop, manufacturers are making the process of unlocking a phone as user-friendly as possible. To unlock its new phone, Arkady's pet dog Mu-mu has to bark the password once. The phon",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF868A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "As technologies develop, manufacturers are making the process of unlocking a phone as user-friendly as possible. To unlock its new phone, Arkady's pet dog Mu-mu has to bark the password once. The phon...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "随着技术的发展，制造商正在使解锁手机的过程尽可能用户友好。为了解锁其新手机，Arkady 的宠物狗 Mu-mu 只需叫出一次密码即可。手机将密码表示为一个由两个小写英文字母组成的字符串。\n\nMu-mu 的敌人 Kashtanka 想要解锁 Mu-mu 的手机以窃取一些敏感信息，但它只能叫出 #cf_span[n] 个不同的单词，每个单词均由两个小写英文字母组成。Kashtanka 想要连续叫出若干...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ p = p_1 p_2 \\in \\{a,\\dots,z\\}^2 $ be the password.  \nLet $ W = \\{w_1, w_2, \\dots, w_n\\} $ be a set of $ n $ distinct words, where each $ w_i = w_{i,1} w_{i,2} \\in \\{a,\\dots,z\\}...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments