AT_abc182_c [ABC182C] To 3

题目描述

给定一个各位数字都不为 $0$ 的正整数 $N$。
设 $N$ 的位数为 $k$。你可以删除 $0$ 个以上、少于 $k$ 个数字，然后将剩下的数字按原顺序拼接，想要得到一个 $3$ 的倍数。
请判断是否可以得到 $3$ 的倍数，如果可以，求出所需删除的最少数字个数。

输入格式

输入为以下格式，从标准输入读入。

$N$

输出格式

如果无法得到 $3$ 的倍数，则输出 $-1$；如果可以，输出所需删除的最少数字个数。

样例 1

输入

35

输出

1

样例 2

输入

369

输出

0

样例 3

输入

6227384

输出

1

样例 4

输入

11

输出

-1

说明/提示

限制

• $1 \leq N < 10^{18}$
• $N$ 是一个各位数字都不为 $0$ 的整数

样例解释 1

删除 $5$ 得到 $3$，$3$ 是 $3$ 的倍数。此时删除的数字个数为 $1$，且最少。

样例解释 2

注意可以一个数字都不删除。

样例解释 3

例如，删除 $8$ 得到 $622734$，$622734$ 是 $3$ 的倍数。

样例解释 4

需要注意，删除的数字个数必须在 $0$ 个以上且少于 $N$ 的位数 $k$，不能全部删除。如果无法得到 $3$ 的倍数，根据题意应输出 $-1$。

由 ChatGPT 4.1 翻译