B. 3-palindrome

Codeforces

IDCF805B

Time1000ms

Memory256MB

Difficulty—

constructive algorithms

English · Original

Chinese · Translation

Formal · Original

In the beginning of the new year Keivan decided to reverse his name. He doesn't like palindromes, so he changed Naviek to Navick. He is too selfish, so for a given _n_ he wants to obtain a string of _n_ characters, each of which is either '_a_', '_b_' or '_c_', with no _palindromes_ of length 3 appearing in the string as a substring. For example, the strings "_abc_" and "_abca_" suit him, while the string "_aba_" doesn't. He also want the number of letters '_c_' in his string to be as little as possible. ## Input The first line contains single integer _n_ (1 ≤ _n_ ≤ 2·105) — the length of the string. ## Output Print the string that satisfies all the constraints. If there are multiple answers, print any of them. [samples] ## Note A _palindrome_ is a sequence of characters which reads the same backward and forward.

在新年开始时，Keivan 决定将他的名字反转。他不喜欢回文，因此他将 Naviek 改为 Navick。他太自私了，所以对于给定的 #cf_span[n]，他希望得到一个长度为 #cf_span[n] 的字符串，每个字符都是 '_a_'、'_b_' 或 '_c_'，且字符串中不包含任何长度为 #cf_span[3] 的回文子串。例如，字符串 "_abc_" 和 "_abca_" 符合他的要求，而字符串 "_aba_" 不符合。他还希望字符串中字母 '_c_' 的数量尽可能少。第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 2·105]）— 字符串的长度。请输出满足所有约束条件的字符串。如果有多个答案，输出任意一个即可。回文是指正读和反读都相同的字符序列。 ## Input 第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 2·105]）— 字符串的长度。 ## Output 请输出满足所有约束条件的字符串。如果有多个答案，输出任意一个即可。 [samples] ## Note 回文是指正读和反读都相同的字符序列。

**Definitions** Let $ n \in \mathbb{Z} $, $ 1 \leq n \leq 2 \cdot 10^5 $, be the length of the string. Let $ S \in \{a, b, c\}^n $ be a string of length $ n $ over the alphabet $ \{a, b, c\} $. **Constraints** 1. $ S $ contains no substring of length 3 that is a palindrome. 2. The number of occurrences of the character $ c $ in $ S $ is minimized. **Objective** Find any string $ S $ satisfying the above constraints.

Samples

Input #1

Output #1

aa

Input #2

Output #2

bba

API Response (JSON)

{
  "problem": {
    "name": "B. 3-palindrome",
    "description": {
      "content": "In the beginning of the new year Keivan decided to reverse his name. He doesn't like palindromes, so he changed Naviek to Navick. He is too selfish, so for a given _n_ he wants to obtain a string of ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF805B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "In the beginning of the new year Keivan decided to reverse his name. He doesn't like palindromes, so he changed Naviek to Navick.\n\nHe is too selfish, so for a given _n_ he wants to obtain a string of ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "在新年开始时，Keivan 决定将他的名字反转。他不喜欢回文，因此他将 Naviek 改为 Navick。\n\n他太自私了，所以对于给定的 #cf_span[n]，他希望得到一个长度为 #cf_span[n] 的字符串，每个字符都是 '_a_'、'_b_' 或 '_c_'，且字符串中不包含任何长度为 #cf_span[3] 的回文子串。例如，字符串 \"_abc_\" 和 \"_abca_\" 符合他的要求...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $, $ 1 \\leq n \\leq 2 \\cdot 10^5 $, be the length of the string.  \nLet $ S \\in \\{a, b, c\\}^n $ be a string of length $ n $ over the alphabet $ \\{a, b, c\\} $.\n\n*...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments