{"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 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$.\n\nFor 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$.\n\nPolycarp 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.\n\nWhat is the maximum number of numbers divisible by $3$ that Polycarp can obtain?\n\n## Input\n\nThe 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_.\n\n## Output\n\nPrint the maximum number of numbers divisible by $3$ that Polycarp can get by making vertical cuts in the given number $s$.\n\n[samples]\n\n## Note\n\nIn the first example, an example set of optimal cuts on the number is _3|1|21_.\n\nIn the second example, you do not need to make any cuts. The specified number _6_ forms one number that is divisible by $3$.\n\nIn 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$.\n\nIn 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$.","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$，那么 Polycarp 可以通过两次切割将其分为三部分：$3 | 1 | 21$。结果，他将得到两个能被 3 整除的数字。\n\nPolycarp 可以在任意相邻数字对之间进行任意数量的垂直切割。得到的数字不能包含前导零（即，数字可以以 _0_ 开头，当且仅当这个数字恰好是单个字符 '_0_'）。例如，_007_、_01_ 和 _00099_ 是无效数字，但 _90_、_0_ 和 _10001_ 是有效的。\n\nPolycarp 最多能获得多少个能被 3 整除的数字？\n\n输入的第一行包含一个正整数 $s$。数字 $s$ 的位数在 $1$ 到 $2 dot.op 10^5$ 之间（包含端点）。最左边（首位）数字不等于 _0_。\n\n请输出 Polycarp 通过对给定数字 $s$ 进行垂直切割所能获得的能被 3 整除的数字的最大数量。\n\n在第一个例子中，最优切割方案的一个示例是 _3|1|21_。\n\n在第二个例子中，你不需要进行任何切割。给定的数字 _6_ 构成一个能被 $3$ 整除的数字。\n\n在第三个例子中，必须在每对相邻数字之间进行切割。结果，Polycarp 得到一个数字 _1_ 和 $33$ 个数字 _0_。每个 $33$ 个数字 _0_ 都构成一个能被 3 整除的数字。\n\n在第四个例子中，最优切割方案的一个示例是 _2|0|1|9|201|81_。数字 $0$、$9$、$201$ 和 $81$ 都能被 3 整除。\n\n## Input\n\n输入的第一行包含一个正整数 $s$。数字 $s$ 的位数在 $1$ 到 $2 dot.op 10^5$ 之间（包含端点）。最左边（首位）数字不等于 _0_。\n\n## Output\n\n请输出 Polycarp 通过对给定数字 $s$ 进行垂直切割所能获得的能被 3 整除的数字的最大数量。\n\n[samples]\n\n## Note\n\n在第一个例子中，最优切割方案的一个示例是 _3|1|21_。在第二个例子中，你不需要进行任何切割。给定的数字 _6_ 构成一个能被 $3$ 整除的数字。在第三个例子中，必须在每对相邻数字之间进行切割。结果，Polycarp 得到一个数字 _1_ 和 $33$ 个数字 _0_。每个 $33$ 个数字 _0_ 都构成一个能被 3 整除的数字。在第四个例子中，最优切割方案的一个示例是 _2|0|1|9|201|81_。数字 $0$、$9$、$201$ 和 $81$ 都能被 3 整除。","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 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\".  \n\nLet $ f(s_i) = 1 $ if the integer value of substring $ s_i $ is divisible by 3, and $ f(s_i) = 0 $ otherwise.  \n\n**Constraints**  \n1. Each substring $ s_i $ must be a valid decimal integer:  \n   - If $ |s_i| > 1 $, then the first digit of $ s_i $ must not be '0'.  \n   - If $ |s_i| = 1 $ and the digit is '0', it is valid.  \n\n**Objective**  \nMaximize the total count of substrings divisible by 3:  \n$$\n\\max \\sum_{i=1}^m f(s_i)\n$$  \nover all valid cut configurations of $ s $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF1005D","tags":["dp","greedy","number theory"],"sample_group":[["3121","2"],["6","1"],["1000000000000000000000000000000000","33"],["201920181","4"]],"created_at":"2026-03-03 11:00:39"}}