← 返回题目列表

Codeforces · 1005/D

D. 坡旅甲和 Div 3

中文机器翻译题面 查看原题

Polycarp 喜欢能被 3 整除的数字。

他有一个巨大的数字$$$s$$$。波利卡普想要从中删除可被 $$$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\cdot10^5$$$ 之间(含)。第一个(最左边)数字不等于 0。

输出

打印 Polycarp 通过对给定数字 $$$s$$$ 进行垂直切割可以得到的可被 $$$3$$$ 整除的最大数字数。

示例

输入 #1

3121

输出 #1

2

输入 #2

6

输出 #2

1

输入 #3

1000000000000000000000000000000000

输出 #3

33

输入#4

201920181

输出#4

4

注意

在第一个示例中,数量上的最佳切割示例集是 3|1|21。

在第二个示例中,您不需要进行任何剪切。指定的数字 6 构成一个可被 $$$3$$$ 整除的数字。

在第三个示例中,必须在每对数字之间进行剪切。结果,Polycarp 得到一位数字 1 和 $$$33$$$ 数字 0。$$$33$$$ 中的每个数字 0 形成一个能被 $$$3$$$ 整除的数字。

在第四个示例中,最佳剪辑的示例集是2|0|1|9|201|81。数字 $$$0$$$、$$$9$$$、$$$201$$$ 和 $$$81$$$ 可以被 $$$3$$$ 整除。