A. Interview with Oleg

Codeforces

IDCF729A

Time1000ms

Memory256MB

Difficulty—

implementationstrings

English · Original

Chinese · Translation

Formal · Original

Polycarp has interviewed Oleg and has written the interview down without punctuation marks and spaces to save time. Thus, the interview is now a string _s_ consisting of _n_ lowercase English letters. There is a filler word _ogo_ in Oleg's speech. All words that can be obtained from _ogo_ by adding _go_ several times to the end of it are also considered to be fillers. For example, the words _ogo_, _ogogo_, _ogogogo_ are fillers, but the words _go_, _og_, _ogog_, _ogogog_ and _oggo_ are not fillers. The fillers have maximal size, for example, for _ogogoo_ speech we can't consider _ogo_ a filler and _goo_ as a normal phrase. We should consider _ogogo_ as a filler here. To print the interview, Polycarp has to replace each of the fillers with three asterisks. Note that a filler word is replaced with exactly three asterisks regardless of its length. Polycarp has dealt with this problem in no time. Can you do the same? The clock is ticking! ## Input The first line contains a positive integer _n_ (1 ≤ _n_ ≤ 100) — the length of the interview. The second line contains the string _s_ of length _n_, consisting of lowercase English letters. ## Output Print the interview text after the replacement of each of the fillers with "_***_". It is allowed for the substring "_***_" to have several consecutive occurences. [samples] ## Note The first sample contains one filler word _ogogo_, so the interview for printing is "_a***b_". The second sample contains two fillers _ogo_ and _ogogogo_. Thus, the interview is transformed to "_***gmg***_".

Polycarp 对 Oleg 进行了采访，并为了节省时间，将采访内容写成了一串没有标点符号和空格的字符串。因此，采访内容现在是一个由 #cf_span[n] 个小写英文字母组成的字符串 #cf_span[s]。 Oleg 的讲话中有一个填充词 _ogo_。所有可以通过在 _ogo_ 末尾添加若干次 _go_ 而得到的单词也被视为填充词。例如，单词 _ogo_、_ogogo_、_ogogogo_ 是填充词，但单词 _go_、_og_、_ogog_、_ogogog_ 和 _oggo_ 不是填充词。填充词具有最大长度，例如，对于字符串 _ogogoo_，我们不能将 _ogo_ 视为填充词而将 _goo_ 视为正常语句。我们必须将 _ogogo_ 视为填充词。为了打印采访内容，Polycarp 必须将每个填充词替换为三个星号。注意，无论填充词的长度如何，它都会被恰好替换为三个星号。 Polycarp 很快解决了这个问题。你能做到吗？时间正在流逝！第一行包含一个正整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 100]) —— 采访的长度。第二行包含一个长度为 #cf_span[n] 的字符串 #cf_span[s]，由小写英文字母组成。请输出将每个填充词替换为 "_***_" 后的采访文本。允许 "_***_" 子串出现连续多次。第一个样例包含一个填充词 _ogogo_，因此打印的采访内容为 "_a***b_"。第二个样例包含两个填充词 _ogo_ 和 _ogogogo_。因此，采访被转换为 "_***gmg***_"。 ## Input 第一行包含一个正整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 100]) —— 采访的长度。第二行包含一个长度为 #cf_span[n] 的字符串 #cf_span[s]，由小写英文字母组成。 ## Output 请输出将每个填充词替换为 "_***_" 后的采访文本。允许 "_***_" 子串出现连续多次。 [samples] ## Note 第一个样例包含一个填充词 _ogogo_，因此打印的采访内容为 "_a***b_"。第二个样例包含两个填充词 _ogo_ 和 _ogogogo_。因此，采访被转换为 "_***gmg***_"。

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the length of the string. Let $ s \in \Sigma^n $ be the input string, where $ \Sigma = \{a, b, \dots, z\} $. A *filler* is a substring of the form $ \texttt{o}(\texttt{go})^k $ for some integer $ k \geq 1 $, i.e., $ \texttt{ogo}, \texttt{ogogo}, \texttt{ogogogo}, \dots $. **Constraints** 1. $ 1 \leq n \leq 100 $ 2. $ s $ consists only of lowercase English letters. **Objective** Replace every *maximal* filler substring in $ s $ with `***`, such that: - A filler is maximal if it cannot be extended further while remaining a filler. - Output the resulting string after all such replacements.

Samples

Input #1

7
aogogob

Output #1

a***b

Input #2

13
ogogmgogogogo

Output #2

***gmg***

Input #3

9
ogoogoogo

Output #3

*********

API Response (JSON)

{
  "problem": {
    "name": "A. Interview with Oleg",
    "description": {
      "content": "Polycarp has interviewed Oleg and has written the interview down without punctuation marks and spaces to save time. Thus, the interview is now a string _s_ consisting of _n_ lowercase English letters.",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF729A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Polycarp has interviewed Oleg and has written the interview down without punctuation marks and spaces to save time. Thus, the interview is now a string _s_ consisting of _n_ lowercase English letters....",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Polycarp 对 Oleg 进行了采访，并为了节省时间，将采访内容写成了一串没有标点符号和空格的字符串。因此，采访内容现在是一个由 #cf_span[n] 个小写英文字母组成的字符串 #cf_span[s]。\n\nOleg 的讲话中有一个填充词 _ogo_。所有可以通过在 _ogo_ 末尾添加若干次 _go_ 而得到的单词也被视为填充词。例如，单词 _ogo_、_ogogo_、_ogogogo_...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the length of the string.  \nLet $ s \\in \\Sigma^n $ be the input string, where $ \\Sigma = \\{a, b, \\dots, z\\} $.  \n\nA *filler* is a substring of the form ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments