H. PepperLa's String

Codeforces

IDCF10280H

Time1000ms

Memory64MB

Difficulty—

English · Original

Formal · Original

PepperLa loves strings.His desire for strings is infinite, but his storage is limited. There is a method to compress strings. A substring whose characters are all the same and are all lower case letters could be compressed into one character plus one hexadecimal number which represents character's counting. (numbers over ten are represented in upper case letters) Here a substring is a string could be obtained by deleting several characters from the begin and end. For example,the string is "aaacccccccccc". compression operations could replace "aaa" with "a3", and repalce "cccccccccc" with "cA". So the compressed string becomes "a3cA". And if you choose 17 'a', you could compress it to "a11", but you can't compress "11" to "12". The method allows lossy compression which means you can miss at most 1 character before you compressing the string. It should be noted that after deleting one character the string is actually not successive.(See sample testcase for details) You can do any times or even zero times of compression operations, find the shortest compressed string, if there are multiple answers, output the one with minimal lexicographic order. There are multiple test cases in this problem. For every test case, the input contains one line, the given string. The input guarantees that strings contains only lower case letters For each test case, $1 < s t r i n g. l e n g t h <= 10^6$, $sum l e n g t h <= 5 times 10^6$ For each test case, output a single line contains the answer string. In first string, if you choose to miss one 'a', the string becomes "aacccccccccc" and compressed string is "a2cA". In second string, if you choose to miss one 'b', the string becomes something like "aaa aaa" the answer is not "a6" but "a3a3". ## Input There are multiple test cases in this problem.For every test case, the input contains one line, the given string.The input guarantees that strings contains only lower case lettersFor each test case, $1 < s t r i n g. l e n g t h <= 10^6$, $sum l e n g t h <= 5 times 10^6$ ## Output For each test case, output a single line contains the answer string. [samples] ## Note In first string, if you choose to miss one 'a', the string becomes "aacccccccccc" and compressed string is "a2cA".In second string, if you choose to miss one 'b', the string becomes something like "aaa aaa" the answer is not "a6" but "a3a3".

**Definitions** Let $ \sigma_k(n) = \sum_{d \mid n} d^k $ for $ k \in \mathbb{N}_0 $, $ n \in \mathbb{Z}^+ $. **Given** Integers $ a, b, n $ such that $ 0 \leq a, b < 4 $ and $ 1 \leq n \leq 10^{12} $. **Objective** Compute: $$ \left( \left( \sum_{i=1}^n \sigma_a(i) \right) \oplus \left( \sum_{i=1}^n \sigma_b(i) \right) \right) \mod 2^{64} $$

API Response (JSON)

{
  "problem": {
    "name": "H. PepperLa's String",
    "description": {
      "content": "PepperLa loves strings.His desire for strings is infinite, but his storage is limited. There is a method to compress strings. A substring whose characters are all the same and are all lower case lett",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 65536
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10280H"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "PepperLa loves strings.His desire for strings is infinite, but his storage is limited.\n\nThere is a method to compress strings. A substring whose characters are all the same and are all lower case lett...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ \\sigma_k(n) = \\sum_{d \\mid n} d^k $ for $ k \\in \\mathbb{N}_0 $, $ n \\in \\mathbb{Z}^+ $.  \n\n**Given**  \nIntegers $ a, b, n $ such that $ 0 \\leq a, b < 4 $ and $ 1 \\leq n \\leq 10...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments