← 返回题目列表

AtCoder · abc182_c

C. 至 3

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

分数: 300 点

问题陈述

给定的是一个正整数 N,其中没有任何数字 0.
让 k 是中的位数 N。我们想要制作多个 3 通过至少擦除 0 最多 k-1 数字来自 N 并连接剩余的数字而不改变顺序。
确定是否可以制作多个 3 这样。如果可能的话,找出必须删除的最少位数才能得到这样的数字。

约束

  • 1 \le N \lt 10^{18}
  • 中没有任何数字 N is 0.

输入

输入由标准输入按以下格式给出:

N

输出

如果不可能生成的倍数 3,打印 相反, -1;否则,打印出必须擦除的最少位数才能得到这样的数字。


示例输入 1

35

示例输出 1

1

通过擦除 5,我们得到数字 3,它是 3。在这里,我们删除了尽可能少的数字 - 1.


示例输入 2

369

示例输出 2

0

请注意,我们可以选择不删除任何数字。


示例输入 3

6227384

示例输出 3

1

例如,通过擦除 8,我们得到数字 622734,它是 3.


示例输入 4

11

示例输出 4

-1

请注意,我们必须至少擦除 0 最多 k-1 数字,其中 k 是中的位数 N,所以我们无法删除所有数字。
在这种情况下,不可能使 3 按照问题陈述中描述的方式,所以我们应该打印 -1.