To 3

题目描述

给定一个正整数 $N$，其各位数字都不为 $0$。
设 $k$ 为 $N$ 的位数。我们想通过擦去至少 $0$ 个且最多 $k-1$ 个数字，并按原顺序连接剩下的数字，来得到一个能被 $3$ 整除的数。
判断是否可以通过这种方式得到一个能被 $3$ 整除的数。如果可以，找出为得到这样的数必须擦去的最少数字个数。

输入格式

输入按标准输入给出，格式如下： $N$

输出格式

如果无法得到能被 $3$ 整除的数，输出 $-1$；否则，输出为得到这样的数必须擦去的最少数字个数。

35

1

369

0

6227384

1

11

-1

提示

$1 \le N \lt 10^{18}$ $N$ 的各位数字都不为 $0$。通过擦去 $5$，可以得到数 $3$，它可以被 $3$ 整除。在这里我们擦去的数字个数最少——$1$。
注意我们可以选择不擦去任何数字。
例如，通过擦去 $8$，可以得到数 $622734$，它可以被 $3$ 整除。
注意我们必须擦去至少 $0$ 个且最多 $k-1$ 个数字，这里 $k$ 是 $N$ 的位数，所以我们不能把所有数字都擦去。
在这种情况下，无法按问题所述的方式得到能被 $3$ 整除的数，因此应输出 $-1$。

标签: AtCoder|abc182C

来源

AtCoder|abc182C