J. palprime

Codeforces

IDCF10088J

Time4000ms

Memory24MB

Difficulty—

English · Original

Formal · Original

A palindromic prime (sometimes called a palprime) is a prime number that is also a palindromic number. Palindromicity depends on the base of the numbering system and its writing conventions, while primality is independent of such concerns. The sequence of binary palindromic primes begins(in binary): 11, 101, 111, 10001, 11111, 1001001 You are given a number b (in binary), you should output the first palprime greater than or equal to b. The input consists of multiple test cases, each test case consists of a number b in binary. We guarantee b will be no Longer than 21 bits The first palprime greater than or equal to b ## Input The input consists of multiple test cases, each test case consists of a number b in binary. We guarantee b will be no Longer than 21 bits ## Output The first palprime greater than or equal to b [samples]

**Definitions** Let $ T = (V, E, w) $ be a weighted undirected tree with $ |V| = N $, where $ w: E \to \mathbb{Z}^+ $ is the edge weight function. Let $ S \subseteq V $ be a dynamic subset of "special" cities. **Constraints** 1. $ 1 \leq N \leq 10^5 $ 2. $ 1 \leq Q \leq 10^5 $ 3. Total sum of $ |S| $ over all type-2 queries $ \leq 5 \cdot 10^5 $ 4. Edge weights $ w(e) \in [1, 10^9] $ **Operations** - **Type 1**: Toggle membership of a city $ c \in V $ in $ S $: $ S \leftarrow S \oplus \{c\} $ - **Type 2**: Given $ S $, for each $ v \in S $, compute: $$ f(v) = \max_{u \in S \setminus \{v\}} \text{dist}(v, u) $$ where $ \text{dist}(v, u) $ is the sum of edge weights along the unique path between $ v $ and $ u $ in $ T $. **Objective** For each type-2 query, output $ f(v) $ for every $ v \in S $ in the order given in the query.

API Response (JSON)

{
  "problem": {
    "name": "J. palprime",
    "description": {
      "content": "A palindromic prime (sometimes called a palprime) is a prime number that is also a palindromic number. Palindromicity depends on the base of the numbering system and its writing conventions, while pri",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 24576
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10088J"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "A palindromic prime (sometimes called a palprime) is a prime number that is also a palindromic number. Palindromicity depends on the base of the numbering system and its writing conventions, while pri...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T = (V, E, w) $ be a weighted undirected tree with $ |V| = N $, where $ w: E \\to \\mathbb{Z}^+ $ is the edge weight function.  \nLet $ S \\subseteq V $ be a dynamic subset of \"spe...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments