B. Code obfuscation

Codeforces

IDCF765B

Time2000ms

Memory512MB

Difficulty—

greedyimplementationstrings

English · Original

Chinese · Translation

Formal · Original

Kostya likes Codeforces contests very much. However, he is very disappointed that his solutions are frequently hacked. That's why he decided to obfuscate (intentionally make less readable) his code before upcoming contest. To obfuscate the code, Kostya first looks at the first variable name used in his program and replaces all its occurrences with a single symbol _a_, then he looks at the second variable name that has not been replaced yet, and replaces all its occurrences with _b_, and so on. Kostya is well-mannered, so he doesn't use any one-letter names before obfuscation. Moreover, there are at most 26 unique identifiers in his programs. You are given a list of identifiers of some program with removed spaces and line breaks. Check if this program can be a result of Kostya's obfuscation. ## Input In the only line of input there is a string _S_ of lowercase English letters (1 ≤ |_S_| ≤ 500) — the identifiers of a program with removed whitespace characters. ## Output If this program can be a result of Kostya's obfuscation, print "_YES_" (without quotes), otherwise print "_NO_". [samples] ## Note In the first sample case, one possible list of identifiers would be "_number string number character number string number_". Here how Kostya would obfuscate the program: * replace all occurences of _number_ with _a_, the result would be "_a string a character a string a_", * replace all occurences of _string_ with _b_, the result would be "_a b a character a b a_", * replace all occurences of _character_ with _c_, the result would be "_a b a c a b a_", * all identifiers have been replaced, thus the obfuscation is finished.

Kostya 非常喜欢 Codeforces 比赛。然而，他非常失望的是，他的解决方案经常被 hack。因此，他决定在即将到来的比赛前对代码进行混淆（故意降低可读性）。为了混淆代码，Kostya 首先查看程序中使用的第一个变量名，并将其所有出现替换为单个符号 #cf_span[a]，然后查看尚未被替换的第二个变量名，并将其所有出现替换为 #cf_span[b]，依此类推。Kostya 是个有礼貌的人，因此在混淆前他不会使用任何单字母名称。此外，他的程序中最多有 26 个唯一标识符。你被给定一个移除了空格和换行符的程序标识符列表。请判断这个程序是否可能是 Kostya 混淆的结果。输入的唯一一行包含一个由小写英文字母组成的字符串 #cf_span[S]（#cf_span[1 ≤ |S| ≤ 500]）——移除了空白字符后的程序标识符。如果这个程序可能是 Kostya 混淆的结果，请输出 "_YES_"（不含引号），否则输出 "_NO_"。在第一个样例中，一个可能的标识符列表是 "_number string number character number string number_"。Kostya 混淆程序的过程如下： ## Input 在输入的唯一一行中，给出一个由小写英文字母组成的字符串 #cf_span[S]（#cf_span[1 ≤ |S| ≤ 500]）——移除了空白字符后的程序标识符。 ## Output 如果这个程序可能是 Kostya 混淆的结果，请输出 "_YES_"（不含引号），否则输出 "_NO_"。 [samples] ## Note 在第一个样例中，一个可能的标识符列表是 "_number string number character number string number_"。Kostya 混淆程序的过程如下：将所有 _number_ 的出现替换为 _a_，结果为 "_a string a character a string a_"；将所有 _string_ 的出现替换为 _b_，结果为 "_a b a character a b a_"；将所有 _character_ 的出现替换为 _c_，结果为 "_a b a c a b a_"；所有标识符均已替换，混淆完成。

Let $ S $ be a string of lowercase English letters of length $ |S| \in [1, 500] $. Define a mapping $ f: \mathbb{N} \to \{a, b, c, \dots\} $ (at most 26 distinct symbols) such that: - The first distinct identifier in the original program (by order of first occurrence) is mapped to `a`, - The second distinct identifier is mapped to `b`, - And so on, in strictly increasing alphabetical order of replacement symbols. The obfuscated string $ S $ must satisfy: - The first occurrence of any letter in $ S $ must appear in strictly increasing alphabetical order. - That is, if we let $ \text{first}(c) $ denote the index of the first occurrence of character $ c \in S $, then for any two distinct characters $ c_1, c_2 \in S $, if $ c_1 < c_2 $ lexicographically, then $ \text{first}(c_1) < \text{first}(c_2) $. Equivalently: Let $ C = \{ c \in S \mid c \text{ is a lowercase letter} \} $ be the set of distinct characters in $ S $. Sort $ C $ in increasing alphabetical order: $ c_1 < c_2 < \dots < c_k $. Then $ S $ is a valid obfuscation if and only if: $$ \forall i \in \{1, 2, \dots, k\}, \quad \text{the first occurrence of } c_i \text{ in } S \text{ occurs before the first occurrence of } c_{i+1}. $$ **Output:** - `_YES_` if the above condition holds, - `_NO_` otherwise.

Samples

Input #1

abacaba

Output #1

YES

Input #2

jinotega

Output #2

NO

API Response (JSON)

{
  "problem": {
    "name": "B. Code obfuscation",
    "description": {
      "content": "Kostya likes Codeforces contests very much. However, he is very disappointed that his solutions are frequently hacked. That's why he decided to obfuscate (intentionally make less readable) his code be",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF765B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Kostya likes Codeforces contests very much. However, he is very disappointed that his solutions are frequently hacked. That's why he decided to obfuscate (intentionally make less readable) his code be...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Kostya 非常喜欢 Codeforces 比赛。然而，他非常失望的是，他的解决方案经常被 hack。因此，他决定在即将到来的比赛前对代码进行混淆（故意降低可读性）。\n\n为了混淆代码，Kostya 首先查看程序中使用的第一个变量名，并将其所有出现替换为单个符号 #cf_span[a]，然后查看尚未被替换的第二个变量名，并将其所有出现替换为 #cf_span[b]，依此类推。Kostya 是个有礼...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ S $ be a string of lowercase English letters of length $ |S| \\in [1, 500] $.\n\nDefine a mapping $ f: \\mathbb{N} \\to \\{a, b, c, \\dots\\} $ (at most 26 distinct symbols) such that:\n- The first disti...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments