C. Did you mean...

Codeforces

IDCF861C

Time1000ms

Memory256MB

Difficulty—

brute forceimplementationstrings

English · Original

Chinese · Translation

Formal · Original

Beroffice text editor has a wide range of features that help working with text. One of the features is an automatic search for typos and suggestions of how to fix them. Beroffice works only with small English letters (i.e. with 26 letters from _a_ to _z_). Beroffice thinks that a word is typed with a typo if there are three or more consonants in a row in the word. The only exception is that if the block of consonants has all letters the same, then this block (even if its length is greater than three) is not considered a typo. Formally, a word is typed with a typo if there is a block of not less that three consonants in a row, and there are at least two different letters in this block. For example: * the following words have typos: "_hellno_", "_hackcerrs_" and "_backtothefutttture_"; * the following words don't have typos: "_helllllooooo_", "_tobeornottobe_" and "_oooooo_". When Beroffice editor finds a word with a typo, it inserts as little as possible number of spaces in this word (dividing it into several words) in such a way that each of the resulting words is typed without any typos. Implement this feature of Beroffice editor. Consider the following letters as the only vowels: '_a_', '_e_', '_i_', '_o_' and '_u_'. All the other letters are consonants in this problem. ## Input The only line contains a non-empty word consisting of small English letters. The length of the word is between 1 and 3000 letters. ## Output Print the given word without any changes if there are no typos. If there is at least one typo in the word, insert the minimum number of spaces into the word so that each of the resulting words doesn't have any typos. If there are multiple solutions, print any of them. [samples]

[{"iden":"statement","content":"Beroffice 文本编辑器具有多种有助于文本处理的功能，其中之一是自动检测拼写错误并提供修正建议。\n\nBeroffice 仅处理小写英文字母（即从 _a_ 到 _z_ 的 26 个字母）。Beroffice 认为，如果一个单词中存在三个或更多连续的辅音字母，则该单词存在拼写错误。唯一的例外是：如果连续的辅音块中所有字母都相同，则该块（即使长度超过三）不被视为拼写错误。形式化地说，一个单词存在拼写错误，当且仅当存在一个长度不少于三的连续辅音块，且该块中至少包含两个不同的字母。\n\n例如：\n\n当 Beroffice 编辑器发现一个存在拼写错误的单词时，它会在该单词中插入尽可能少的空格（将其分割为多个单词），使得每个 resulting 单词都不包含任何拼写错误。\n\n请实现 Beroffice 编辑器的这一功能。本题中，仅将以下字母视为元音：'_a_'、'_e_'、'_i_'、'_o_' 和 '_u_'。其余所有字母均为辅音。\n\n输入仅有一行，包含一个由小写英文字母组成的非空单词。单词长度在 #cf_span[1] 到 #cf_span[3000] 之间。\n\n如果没有拼写错误，请原样输出该单词。\n\n如果单词中至少存在一个拼写错误，请在单词中插入最少数量的空格，使得每个 resulting 单词都不包含任何拼写错误。如果有多种解决方案，输出任意一种即可。"},{"iden":"input","content":"The only line contains a non-empty word consisting of small English letters. The length of the word is between #cf_span[1] and #cf_span[3000] letters."},{"iden":"output","content":"Print the given word without any changes if there are no typos.If there is at least one typo in the word, insert the minimum number of spaces into the word so that each of the resulting words doesn't have any typos. If there are multiple solutions, print any of them."},{"iden":"examples","content":"InputhellnoOutputhell no InputabacabaOutputabacaba InputasdfasdfOutputasd fasd f "}]"

**Definitions** Let $ w = w_1 w_2 \dots w_n $ be a string of length $ n \in [1, 3000] $, where each $ w_i \in \{a, b, \dots, z\} $. Let $ V = \{a, e, i, o, u\} $ be the set of vowels; all other letters are consonants. A **typo** occurs in a contiguous substring $ w_i w_{i+1} \dots w_j $ if: - $ j - i + 1 \geq 3 $, - $ w_k \notin V $ for all $ k \in \{i, \dots, j\} $, - Not all characters in $ w_i \dots w_j $ are identical. **Constraints** - $ 1 \leq n \leq 3000 $ - Each $ w_i \in \{a, b, \dots, z\} $ **Objective** Insert the **minimum number of spaces** into $ w $ to partition it into contiguous substrings (words) such that **no substring contains a typo**. Output any such valid partition.

Samples

Input #1

hellno

Output #1

hell no

Input #2

abacaba

Output #2

abacaba

Input #3

asdfasdf

Output #3

asd fasd f

API Response (JSON)

{
  "problem": {
    "name": "C. Did you mean...",
    "description": {
      "content": "Beroffice text editor has a wide range of features that help working with text. One of the features is an automatic search for typos and suggestions of how to fix them. Beroffice works only with smal",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF861C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Beroffice text editor has a wide range of features that help working with text. One of the features is an automatic search for typos and suggestions of how to fix them.\n\nBeroffice works only with smal...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "[{\"iden\":\"statement\",\"content\":\"Beroffice 文本编辑器具有多种有助于文本处理的功能，其中之一是自动检测拼写错误并提供修正建议。\\n\\nBeroffice 仅处理小写英文字母（即从 _a_ 到 _z_ 的 26 个字母）。Beroffice 认为，如果一个单词中存在三个或更多连续的辅音字母，则该单词存在拼写错误。唯一的例外是：如果连续的辅音块中所有字母都相同，...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ w = w_1 w_2 \\dots w_n $ be a string of length $ n \\in [1, 3000] $, where each $ w_i \\in \\{a, b, \\dots, z\\} $.  \nLet $ V = \\{a, e, i, o, u\\} $ be the set of vowels; all other le...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments