H. Designation in the Mafia

Codeforces

IDCF10073H

Time1000ms

Memory64MB

Difficulty—

English · Original

Formal · Original

The Shitalian mafia has a very peculiar way to name a new associate. The newbie goes through tests to measure his strength, agility, sagacity and influence. The size of the nickname is defined by the results of the tests. Then, the newbie chooses the characters of his nickname, that is, letters from the alphabet. But Shi has nothing better to do, so he demands that the nickname is transformed in a palindrome. A palindrome is a string that can be read the same way if we reverse it. For instance BANANAB is a palindrome, and BANANAS is not. Everything in Shitalia has a cost, including transforming characters. You will receive a matrix P, of size 26x26. The element Pij is the cost of transforming the i-th letter of the alphabet into the j-th letter of the alphabet. You can apply as many transformations as you want. Find the minimum cost to transform the nickname into a palindrome. The first 26 lines form the matrix P. Each line i contains exactly 26 integers Pij (0 ≤ Pij ≤ 106), indicating . The last line contains the nickname that the newbie has chosen, which is a string with n (1 ≤ n ≤ 106) lowercase letters. Print the minimal cost to transform the nickname into a palindrome. ## Input The first 26 lines form the matrix P. Each line i contains exactly 26 integers Pij (0 ≤ Pij ≤ 106), indicating . The last line contains the nickname that the newbie has chosen, which is a string with n (1 ≤ n ≤ 106) lowercase letters. ## Output Print the minimal cost to transform the nickname into a palindrome. [samples]

**Definitions** Let $ K \in \mathbb{Z}^+ $ with $ 1 \leq K \leq 13 $. Let $ B = \{b_1, b_2, \dots, b_K\} $ be a set of integer bases with $ 2 \leq b_i \leq 10^5 $. A number $ X \in \mathbb{N}_0 $ is **K-palindrome** if there exists at least one $ b \in B $ such that the base-$ b $ representation of $ X $ is a palindrome. **Constraints** 1. $ 1 \leq K \leq 13 $ 2. $ 2 \leq b_i \leq 10^5 $ for all $ i \in \{1, \dots, K\} $ 3. $ 1 \leq Q \leq 10^5 $ 4. For each query, $ 0 \leq L \leq U \leq 10^8 $ **Objective** For each query $ (L, U) $, compute: $$ \left| \left\{ X \in \mathbb{N}_0 \cap [L, U] \mid \exists\, b \in B \text{ such that } \text{repr}_b(X) \text{ is a palindrome} \right\} \right| $$

API Response (JSON)

{
  "problem": {
    "name": "H. Designation in the Mafia",
    "description": {
      "content": "The Shitalian mafia has a very peculiar way to name a new associate. The newbie goes through tests to measure his strength, agility, sagacity and influence. The size of the nickname is defined by the ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 65536
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10073H"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "The Shitalian mafia has a very peculiar way to name a new associate. The newbie goes through tests to measure his strength, agility, sagacity and influence. The size of the nickname is defined by the ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ K \\in \\mathbb{Z}^+ $ with $ 1 \\leq K \\leq 13 $.  \nLet $ B = \\{b_1, b_2, \\dots, b_K\\} $ be a set of integer bases with $ 2 \\leq b_i \\leq 10^5 $.  \nA number $ X \\in \\mathbb{N}_0 ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments