L. Ministry of Truth

Codeforces

IDCF10018L

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Andrey works in the Ministry of Truth. His work is changing articles in newspapers and magazines so that they praise the Party and Big Brother. Recently Big Brother decided that it would be fine if all words in all articles are read equally both from right to left and from left to right. In his opinion it will greatly simplify the reading of articles — even if the word is read in the reverse order, its sense won't change. Andrey spends one second to erase one letter from the word and write another one to its place. Only one word left to be changed, after that he will complete the plan and be able to go home. Of course, he wants to do it as soon as possible. But the truth is that he does not clearly understand right now which word he should get after the replacement. Help him to find it out. Input contains a single line with the word that Andrey has to change. The word consists of lowercase Latin letters and its length is from 1 to 200000, inclusively. Output the word which should be a result of Andrey's work. If there are several possible such words, output any of them. ## Input Input contains a single line with the word that Andrey has to change. The word consists of lowercase Latin letters and its length is from 1 to 200000, inclusively. ## Output Output the word which should be a result of Andrey's work. If there are several possible such words, output any of them. [samples]

**Definitions** Let $ w = w_1 w_2 \dots w_n $ be a string of length $ n \in [1, 200000] $, where each $ w_i \in \{a, b, \dots, z\} $. **Objective** Find a palindrome $ p = p_1 p_2 \dots p_n $ such that the number of positions $ i $ where $ w_i \ne p_i $ is minimized. **Constraint** $ p $ must satisfy $ p_i = p_{n+1-i} $ for all $ i \in \{1, \dots, n\} $.

API Response (JSON)

{
  "problem": {
    "name": "L. Ministry of Truth",
    "description": {
      "content": "Andrey works in the Ministry of Truth. His work is changing articles in newspapers and magazines so that they praise the Party and Big Brother. Recently Big Brother decided that it would be fine if a",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10018L"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Andrey works in the Ministry of Truth. His work is changing articles in newspapers and magazines so that they praise the Party and Big Brother.\n\nRecently Big Brother decided that it would be fine if a...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ w = w_1 w_2 \\dots w_n $ be a string of length $ n \\in [1, 200000] $, where each $ w_i \\in \\{a, b, \\dots, z\\} $.\n\n**Objective**  \nFind a palindrome $ p = p_1 p_2 \\dots p_n $ suc...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments