A. Accept or Reject

Codeforces

IDCF10244A

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

This semester, various UFPE competitors had classes of a discipline called Theoretical Informatics. One of the major studied concepts was _Turing Machines (TM)_. A _TM_ is basically a system that has a tape with infinite memory cells to the right and a head pointer that is always pointing to one cell at a given moment. A known fact in computer science is that every algorithm has an equivalent _TM_. There are many _TM_ variations and some of them has capability differences. One of these variations are the _Deciders_, which are machines that always stops (never entering infinite loop state), "accepting" or "rejecting" any given input. One of the recommended exercises of the discipline was the following: "Describe a _Decider_ that accepts a given input string of size $N$ if it has an $M$ sized palindrome as substring and reject if not". Your task here is to solve this exercise, but as we do not have compilers that can interpret _TM_ descriptions, you instead has to code an equivalent algorithm to solve it. The input will contain only one test set. You will receive two integers N and M ($1 <= M <= N <= 5 dot.op 10^5$), as described above, followed by a line with a string $S$ of size $N$. It is guaranteed that $S$ contains only lowercase english letters. The output must contain only one line with "Accept" (without quotes) if your _Decider_ accepts the input or "Reject" (without quotes) if it doesn't. You may print every letter in any case you want (so, for example, the strings Accept, accept, ACcept and accEpT will all be recognized as a positive answer). ## Input The input will contain only one test set. You will receive two integers N and M ($1 <= M <= N <= 5 dot.op 10^5$), as described above, followed by a line with a string $S$ of size $N$. It is guaranteed that $S$ contains only lowercase english letters. ## Output The output must contain only one line with "Accept" (without quotes) if your _Decider_ accepts the input or "Reject" (without quotes) if it doesn't.You may print every letter in any case you want (so, for example, the strings Accept, accept, ACcept and accEpT will all be recognized as a positive answer). [samples]

**Definitions** Let $ N, M \in \mathbb{Z} $ such that $ 1 \leq M \leq N \leq 5 \cdot 10^5 $. Let $ S \in \Sigma^N $ be a string over $ \Sigma = \{a, b, \dots, z\} $. **Constraints** $ 1 \leq M \leq N \leq 5 \cdot 10^5 $, and $ S $ consists only of lowercase English letters. **Objective** Determine whether there exists a substring $ S[i:i+M] $ (for some $ i \in \{0, \dots, N-M\} $) that is a palindrome. If yes, output "Accept"; otherwise, output "Reject".

API Response (JSON)

{
  "problem": {
    "name": "A. Accept or Reject",
    "description": {
      "content": "This semester, various UFPE competitors had classes of a discipline called Theoretical Informatics. One of the major studied concepts was _Turing Machines (TM)_.  A _TM_ is basically a system that ha",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10244A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "This semester, various UFPE competitors had classes of a discipline called Theoretical Informatics. One of the major studied concepts was _Turing Machines (TM)_. \n\nA _TM_ is basically a system that ha...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N, M \\in \\mathbb{Z} $ such that $ 1 \\leq M \\leq N \\leq 5 \\cdot 10^5 $.  \nLet $ S \\in \\Sigma^N $ be a string over $ \\Sigma = \\{a, b, \\dots, z\\} $.\n\n**Constraints**  \n$ 1 \\leq M ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments