A. Shockers

Codeforces

IDCF906A

Time2000ms

Memory256MB

Difficulty—

implementationstrings

English · Original

Chinese · Translation

Formal · Original

Valentin participates in a show called "Shockers". The rules are quite easy: jury selects one letter which Valentin doesn't know. He should make a small speech, but every time he pronounces a word that contains the selected letter, he receives an electric shock. He can make guesses which letter is selected, but for each incorrect guess he receives an electric shock too. The show ends when Valentin guesses the selected letter correctly. Valentin can't keep in mind everything, so he could guess the selected letter much later than it can be uniquely determined and get excessive electric shocks. Excessive electric shocks are those which Valentin got after the moment the selected letter can be uniquely determined. You should find out the number of excessive electric shocks. ## Input The first line contains a single integer _n_ (1 ≤ _n_ ≤ 105) — the number of actions Valentin did. The next _n_ lines contain descriptions of his actions, each line contains description of one action. Each action can be of one of three types: 1. Valentin pronounced some word and didn't get an electric shock. This action is described by the string "_. w_" (without quotes), in which "_._" is a dot (ASCII-code 46), and _w_ is the word that Valentin said. 2. Valentin pronounced some word and got an electric shock. This action is described by the string "_! w_" (without quotes), in which "_!_" is an exclamation mark (ASCII-code 33), and _w_ is the word that Valentin said. 3. Valentin made a guess about the selected letter. This action is described by the string "_? s_" (without quotes), in which "_?_" is a question mark (ASCII-code 63), and _s_ is the guess — a lowercase English letter. All words consist only of lowercase English letters. The total length of all words does not exceed 105. It is guaranteed that last action is a guess about the selected letter. Also, it is guaranteed that Valentin didn't make correct guesses about the selected letter before the last action. Moreover, it's guaranteed that if Valentin got an electric shock after pronouncing some word, then it contains the selected letter; and also if Valentin didn't get an electric shock after pronouncing some word, then it does not contain the selected letter. ## Output Output a single integer — the number of electric shocks that Valentin could have avoided if he had told the selected letter just after it became uniquely determined. [samples] ## Note In the first test case after the first action it becomes clear that the selected letter is one of the following: _a_, _b_, _c_. After the second action we can note that the selected letter is not _a_. Valentin tells word "b" and doesn't get a shock. After that it is clear that the selected letter is _c_, but Valentin pronounces the word _cd_ and gets an excessive electric shock. In the second test case after the first two electric shocks we understand that the selected letter is _e_ or _o_. Valentin tries some words consisting of these letters and after the second word it's clear that the selected letter is _e_, but Valentin makes 3 more actions before he makes a correct hypothesis. In the third example the selected letter can be uniquely determined only when Valentin guesses it, so he didn't get excessive electric shocks.

Valentin 参加了一个名为 "Shockers" 的节目。规则很简单：评委选定一个 Valentin 不知道的字母。他需要发表一段简短的演讲，但每当他说出包含该选定字母的单词时，就会受到电击。他可以猜测选定的字母是什么，但每次错误的猜测也会导致电击。当 Valentin 正确猜出选定字母时，节目结束。 Valentin 无法记住所有信息，因此他可能在选定字母已经可以唯一确定很久之后才做出猜测，从而遭受过多的电击。过多的电击是指在选定字母已经可以唯一确定之后，Valentin 所遭受的电击。你需要计算出这些过多的电击数量。第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 10^5]）——表示 Valentin 执行的动作数量。接下来的 #cf_span[n] 行描述了他的每个动作，每行描述一个动作。每个动作可以是以下三种类型之一：所有单词仅由小写英文字母组成。所有单词的总长度不超过 #cf_span[10^5]。保证最后一个动作是关于选定字母的猜测。同时保证在最后一个动作之前，Valentin 没有做出过任何正确的猜测。此外，保证如果 Valentin 在说出某个单词后受到电击，则该单词包含选定字母；如果他没有受到电击，则该单词不包含选定字母。请输出一个整数——如果 Valentin 在选定字母刚能被唯一确定时立即说出它，他本可以避免的电击次数。 ## Input 第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 10^5]）——表示 Valentin 执行的动作数量。接下来的 #cf_span[n] 行描述了他的每个动作，每行描述一个动作。每个动作可以是以下三种类型之一： Valentin 说出某个单词且未受到电击。此动作由字符串 "_. w_"（不含引号）描述，其中 "_._" 是一个点（ASCII 码为 46），#cf_span[w] 是 Valentin 说出的单词。 Valentin 说出某个单词并受到电击。此动作由字符串 "_! w_"（不含引号）描述，其中 "_!_" 是一个感叹号（ASCII 码为 33），#cf_span[w] 是 Valentin 说出的单词。 Valentin 对选定字母做出猜测。此动作由字符串 "_? s_"（不含引号）描述，其中 "_?_" 是一个问号（ASCII 码为 63），#cf_span[s] 是他的猜测——一个小写英文字母。所有单词仅由小写英文字母组成。所有单词的总长度不超过 #cf_span[10^5]。保证最后一个动作是关于选定字母的猜测。同时保证在最后一个动作之前，Valentin 没有做出过任何正确的猜测。此外，保证如果 Valentin 在说出某个单词后受到电击，则该单词包含选定字母；如果他没有受到电击，则该单词不包含选定字母。 ## Output 输出一个整数——如果 Valentin 在选定字母刚能被唯一确定时立即说出它，他本可以避免的电击次数。 [samples] ## Note 在第一个测试用例中，第一次动作后可以确定选定字母是以下之一：#cf_span[a, b, c]。第二次动作后，我们可以确定选定字母不是 #cf_span[a]。Valentin 说出单词 "b" 且未受到电击。此后可以确定选定字母是 #cf_span[c]，但 Valentin 说出了单词 #cf_span[cd] 并遭受了一次过多的电击。在第二个测试用例中，前两次电击后我们得知选定字母是 #cf_span[e] 或 #cf_span[o]。Valentin 尝试了一些仅包含这些字母的单词，在第二次单词后可以确定选定字母是 #cf_span[e]，但 Valentin 在做出正确猜测前又进行了三次动作。在第三个例子中，选定字母只有在 Valentin 猜测时才能被唯一确定，因此他没有遭受任何过多的电击。

**Definitions** Let $ n \in \mathbb{Z} $ be the number of actions. Let $ A = (a_1, a_2, \dots, a_n) $ be the sequence of actions, where each $ a_i $ is one of: - A word $ w_i $ (Valentin speaks), - A guess $ g_i $ (Valentin guesses a letter). Let $ \Sigma = \{a, b, \dots, z\} $ be the set of 26 lowercase English letters. Let $ L \in \Sigma $ be the hidden selected letter (unknown initially). Let $ S \subseteq \Sigma $ be the set of possible candidates for $ L $, initialized as $ S = \Sigma $. **Constraints** 1. $ 1 \leq n \leq 10^5 $ 2. Total length of all words $ \leq 10^5 $ 3. The last action $ a_n $ is a correct guess: $ g_n = L $ 4. All prior guesses $ g_i $ ($ i < n $) are incorrect: $ g_i \neq L $ 5. For each word $ w_i $: - If Valentin receives a shock, then $ w_i \cap S \neq \emptyset $ and $ L \in w_i $ - If no shock, then $ L \notin w_i $ 6. For each guess $ g_i $: - If shock, then $ g_i \neq L $ - If no shock, then $ g_i = L $ (only occurs at $ i = n $) **Objective** Compute the number of **excessive electric shocks**, defined as: $$ \sum_{i=1}^{n-1} \mathbb{I}_{\{ |S| > 1 \land a_i \text{ causes shock} \}} $$ where $ S $ is updated after each action: - If $ a_i $ is a word $ w_i $: - If shock: $ S \leftarrow S \cap \text{letters}(w_i) $ - If no shock: $ S \leftarrow S \setminus \text{letters}(w_i) $ - If $ a_i $ is a guess $ g_i $: - $ S \leftarrow S \setminus \{g_i\} $ Excessive shocks = number of shocks received **after** $ |S| $ becomes 1 (i.e., $ L $ is uniquely determined) and **before** the final correct guess.

Samples

Input #1

5
! abc
. ad
. b
! cd
? c

Output #1

Input #2

8
! hello
! codeforces
? c
. o
? d
? h
. l
? e

Output #2

Input #3

7
! ababahalamaha
? a
? b
? a
? b
? a
? h

Output #3

API Response (JSON)

{
  "problem": {
    "name": "A. Shockers",
    "description": {
      "content": "Valentin participates in a show called \"Shockers\". The rules are quite easy: jury selects one letter which Valentin doesn't know. He should make a small speech, but every time he pronounces a word tha",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF906A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Valentin participates in a show called \"Shockers\". The rules are quite easy: jury selects one letter which Valentin doesn't know. He should make a small speech, but every time he pronounces a word tha...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Valentin 参加了一个名为 \"Shockers\" 的节目。规则很简单：评委选定一个 Valentin 不知道的字母。他需要发表一段简短的演讲，但每当他说出包含该选定字母的单词时，就会受到电击。他可以猜测选定的字母是什么，但每次错误的猜测也会导致电击。当 Valentin 正确猜出选定字母时，节目结束。\n\nValentin 无法记住所有信息，因此他可能在选定字母已经可以唯一确定很久之后才做出猜...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of actions.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be the sequence of actions, where each $ a_i $ is one of:  \n- A word $ w_i $ (Valentin speaks)...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments