D. Polycarp and Div 3

Codeforces

IDCF1005D

Time3000ms

Memory256MB

Difficulty—

dpgreedynumber theory

English · Original

Chinese · Translation

Formal · Original

Polycarp likes numbers that are divisible by 3. He has a huge number $s$. Polycarp wants to cut from it the maximum number of numbers that are divisible by $3$. To do this, he makes an arbitrary number of vertical cuts between pairs of adjacent digits. As a result, after $m$ such cuts, there will be $m+1$ parts in total. Polycarp analyzes each of the obtained numbers and finds the number of those that are divisible by $3$. For example, if the original number is $s=3121$, then Polycarp can cut it into three parts with two cuts: $3|1|21$. As a result, he will get two numbers that are divisible by $3$. Polycarp can make an arbitrary number of vertical cuts, where each cut is made between a pair of adjacent digits. The resulting numbers cannot contain extra leading zeroes (that is, the number can begin with _0_ if and only if this number is exactly one character '_0_'). For example, _007_, _01_ and _00099_ are not valid numbers, but _90_, _0_ and _10001_ are valid. What is the maximum number of numbers divisible by $3$ that Polycarp can obtain? ## Input The first line of the input contains a positive integer $s$. The number of digits of the number $s$ is between $1$ and $2\cdot10^5$, inclusive. The first (leftmost) digit is not equal to _0_. ## Output Print the maximum number of numbers divisible by $3$ that Polycarp can get by making vertical cuts in the given number $s$. [samples] ## Note In the first example, an example set of optimal cuts on the number is _3|1|21_. In the second example, you do not need to make any cuts. The specified number _6_ forms one number that is divisible by $3$. In the third example, cuts must be made between each pair of digits. As a result, Polycarp gets one digit _1_ and $33$ digits _0_. Each of the $33$ digits _0_ forms a number that is divisible by $3$. In the fourth example, an example set of optimal cuts is _2|0|1|9|201|81_. The numbers $0$, $9$, $201$ and $81$ are divisible by $3$.

Polycarp 喜欢能被 3 整除的数字。他有一个巨大的数字 $s$。Polycarp 希望从其中切割出尽可能多的能被 3 整除的数字。为此，他可以在任意相邻数字对之间进行任意数量的垂直切割。经过 $m$ 次切割后，总共会得到 $m + 1$ 个部分。Polycarp 会分析每个得到的数字，并统计其中能被 3 整除的数字的个数。例如，如果原始数字是 $s = 3121$，那么 Polycarp 可以通过两次切割将其分为三部分：$3 | 1 | 21$。结果，他将得到两个能被 3 整除的数字。 Polycarp 可以在任意相邻数字对之间进行任意数量的垂直切割。得到的数字不能包含前导零（即，数字可以以 _0_ 开头，当且仅当这个数字恰好是单个字符 '_0_'）。例如，_007_、_01_ 和 _00099_ 是无效数字，但 _90_、_0_ 和 _10001_ 是有效的。 Polycarp 最多能获得多少个能被 3 整除的数字？输入的第一行包含一个正整数 $s$。数字 $s$ 的位数在 $1$ 到 $2 dot.op 10^5$ 之间（包含端点）。最左边（首位）数字不等于 _0_。请输出 Polycarp 通过对给定数字 $s$ 进行垂直切割所能获得的能被 3 整除的数字的最大数量。在第一个例子中，最优切割方案的一个示例是 _3|1|21_。在第二个例子中，你不需要进行任何切割。给定的数字 _6_ 构成一个能被 $3$ 整除的数字。在第三个例子中，必须在每对相邻数字之间进行切割。结果，Polycarp 得到一个数字 _1_ 和 $33$ 个数字 _0_。每个 $33$ 个数字 _0_ 都构成一个能被 3 整除的数字。在第四个例子中，最优切割方案的一个示例是 _2|0|1|9|201|81_。数字 $0$、$9$、$201$ 和 $81$ 都能被 3 整除。 ## Input 输入的第一行包含一个正整数 $s$。数字 $s$ 的位数在 $1$ 到 $2 dot.op 10^5$ 之间（包含端点）。最左边（首位）数字不等于 _0_。 ## Output 请输出 Polycarp 通过对给定数字 $s$ 进行垂直切割所能获得的能被 3 整除的数字的最大数量。 [samples] ## Note 在第一个例子中，最优切割方案的一个示例是 _3|1|21_。在第二个例子中，你不需要进行任何切割。给定的数字 _6_ 构成一个能被 $3$ 整除的数字。在第三个例子中，必须在每对相邻数字之间进行切割。结果，Polycarp 得到一个数字 _1_ 和 $33$ 个数字 _0_。每个 $33$ 个数字 _0_ 都构成一个能被 3 整除的数字。在第四个例子中，最优切割方案的一个示例是 _2|0|1|9|201|81_。数字 $0$、$9$、$201$ 和 $81$ 都能被 3 整除。

**Definitions** Let $ s = d_1 d_2 \dots d_n $ be a string of $ n $ digits, where $ d_i \in \{0,1,\dots,9\} $, $ d_1 \neq 0 $, and $ 1 \leq n \leq 2 \cdot 10^5 $. A *cut configuration* is a partition of $ s $ into contiguous non-empty substrings $ s_1, s_2, \dots, s_m $, where $ m \geq 1 $, such that no substring has leading zeros unless it is exactly "0". Let $ f(s_i) = 1 $ if the integer value of substring $ s_i $ is divisible by 3, and $ f(s_i) = 0 $ otherwise. **Constraints** 1. Each substring $ s_i $ must be a valid decimal integer: - If $ |s_i| > 1 $, then the first digit of $ s_i $ must not be '0'. - If $ |s_i| = 1 $ and the digit is '0', it is valid. **Objective** Maximize the total count of substrings divisible by 3: $$ \max \sum_{i=1}^m f(s_i) $$ over all valid cut configurations of $ s $.

Samples

Input #1

Output #1

Input #2

Output #2

Input #3

1000000000000000000000000000000000

Output #3

Input #4

201920181

Output #4

API Response (JSON)

{
  "problem": {
    "name": "D. Polycarp and Div 3",
    "description": {
      "content": "Polycarp likes numbers that are divisible by 3. He has a huge number $s$. Polycarp wants to cut from it the maximum number of numbers that are divisible by $3$. To do this, he makes an arbitrary numb",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF1005D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Polycarp likes numbers that are divisible by 3.\n\nHe has a huge number $s$. Polycarp wants to cut from it the maximum number of numbers that are divisible by $3$. To do this, he makes an arbitrary numb...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Polycarp 喜欢能被 3 整除的数字。\n\n他有一个巨大的数字 $s$。Polycarp 希望从其中切割出尽可能多的能被 3 整除的数字。为此，他可以在任意相邻数字对之间进行任意数量的垂直切割。经过 $m$ 次切割后，总共会得到 $m + 1$ 个部分。Polycarp 会分析每个得到的数字，并统计其中能被 3 整除的数字的个数。\n\n例如，如果原始数字是 $s = 3121$，那么 Polyc...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s = d_1 d_2 \\dots d_n $ be a string of $ n $ digits, where $ d_i \\in \\{0,1,\\dots,9\\} $, $ d_1 \\neq 0 $, and $ 1 \\leq n \\leq 2 \\cdot 10^5 $.  \nA *cut configuration* is a partiti...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments