{"raw_statement":[{"iden":"statement","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?"},{"iden":"input","content":"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_."},{"iden":"output","content":"Print the maximum number of numbers divisible by $3$ that Polycarp can get by making vertical cuts in the given number $s$."},{"iden":"examples","content":"Input\n\n3121\n\nOutput\n\n2\n\nInput\n\n6\n\nOutput\n\n1\n\nInput\n\n1000000000000000000000000000000000\n\nOutput\n\n33\n\nInput\n\n201920181\n\nOutput\n\n4"},{"iden":"note","content":"In 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$."}],"translated_statement":[{"iden":"statement","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 整除。"},{"iden":"input","content":"输入的第一行包含一个正整数 $s$。数字 $s$ 的位数在 $1$ 到 $2 dot.op 10^5$ 之间（包含端点）。最左边（首位）数字不等于 _0_。"},{"iden":"output","content":"请输出 Polycarp 通过对给定数字 $s$ 进行垂直切割所能获得的能被 3 整除的数字的最大数量。"},{"iden":"examples","content":"输入\n3121\n输出\n2\n\n输入\n6\n输出\n1\n\n输入\n1000000000000000000000000000000000\n输出\n33\n\n输入\n201920181\n输出\n4"},{"iden":"note","content":"在第一个例子中，最优切割方案的一个示例是 _3|1|21_。在第二个例子中，你不需要进行任何切割。给定的数字 _6_ 构成一个能被 $3$ 整除的数字。在第三个例子中，必须在每对相邻数字之间进行切割。结果，Polycarp 得到一个数字 _1_ 和 $33$ 个数字 _0_。每个 $33$ 个数字 _0_ 都构成一个能被 3 整除的数字。在第四个例子中，最优切割方案的一个示例是 _2|0|1|9|201|81_。数字 $0$、$9$、$201$ 和 $81$ 都能被 3 整除。"}],"sample_group":[],"show_order":[],"formal_statement":"**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 $.","simple_statement":null,"has_page_source":false}