171. Nearest Palindromes

Codeforces

IDCF10269171

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

A number is called a _palindrome_ if it reads the same forwards and backwards. For example, 5775, 98389, 7, and 66 are palindromes, but 552, 35, and 86867 are not palindromes. Given a number $n$, figure out the closest $k$ palindromes to $n$. If two palindromes have the same distance away from $n$, print the smaller one first. For example, let's say $n$ = 600 and $k$ = 4. The closest palindrome to $n$ is 595, with a distance of 5. The next closest palindrome is 606, with a distance of 6. The next two are 585 (distance of 15) and 616 (distance of 16), so we would print 595, 606, 585, and 616, in that order. The only line of input consists of two space-separated integers $n$ and $k$: the number to check palindromes near, and the number of palindromes to print out, respectively. Output $k$ lines, each consisting of a palindrome, sorted by their distance from $n$ (calculated as abs($n$ - $p$) for a palindrome $p$). *The palindromes must be positive integers*. ## Input The only line of input consists of two space-separated integers $n$ and $k$: the number to check palindromes near, and the number of palindromes to print out, respectively. ## Output Output $k$ lines, each consisting of a palindrome, sorted by their distance from $n$ (calculated as abs($n$ - $p$) for a palindrome $p$).*The palindromes must be positive integers*. [samples]

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the target number, and $ k \in \mathbb{Z}^+ $ be the number of closest palindromes to find. Let $ \mathcal{P} \subset \mathbb{Z}^+ $ be the set of all positive palindromic integers. **Constraints** 1. $ n \geq 1 $ 2. $ k \geq 1 $ 3. All palindromes $ p \in \mathcal{P} $ must satisfy $ p \geq 1 $ **Objective** Find the multiset $ S \subseteq \mathcal{P} $ of size $ k $ such that: - For any $ p_1 \in S $, $ p_2 \in \mathcal{P} \setminus S $, it holds that $ |n - p_1| \leq |n - p_2| $ - If $ |n - p_1| = |n - p_2| $ for $ p_1, p_2 \in \mathcal{P} $, then the smaller palindrome is prioritized - Output the elements of $ S $ sorted by increasing distance $ |n - p| $, and for equal distances, by increasing value of $ p $

API Response (JSON)

{
  "problem": {
    "name": "171. Nearest Palindromes",
    "description": {
      "content": "A number is called a _palindrome_ if it reads the same forwards and backwards. For example, 5775, 98389, 7, and 66 are palindromes, but 552, 35, and 86867 are not palindromes. Given a number $n$, fig",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10269171"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "A number is called a _palindrome_ if it reads the same forwards and backwards. For example, 5775, 98389, 7, and 66 are palindromes, but 552, 35, and 86867 are not palindromes.\n\nGiven a number $n$, fig...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the target number, and $ k \\in \\mathbb{Z}^+ $ be the number of closest palindromes to find.  \nLet $ \\mathcal{P} \\subset \\mathbb{Z}^+ $ be the set of all...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments