Public Judge

pjudge

Time Limit: 1 s Memory Limit: 512 MB Total points: 100

#21691. 【NOIP Round #3】数字

Statistics

题目描述

dottle 是 机器人。

一天,dottle 在黑板上看到了一个十进制整数 $n$,保证 $n$ 的十进制表示中没有 $0$。

dottle 认为,$3$ 的倍数是好的,于是他想要擦掉一些数位上的数字来让 $n$ 变为一个好的数字。

擦数字的过程可以看作删掉 $n$ 十进制表示中的一个数字,然后将剩余部分依次拼接,比如 $114514$ 擦掉从左往右的第三位会变成 $11514$。

注意空的黑板是不合法的,也就是说,假设 $n$ 的十进制表达共有 $k$ 位,执行的删除操作不能超过 $k-1$ 次。

dottle 想要知道,他最少需要擦掉几个数字,才能使 $n$ 变为一个好数,或者告诉他无解。

输入格式

一行一个正整数 $n$。

输出格式

若有解,输出一行一个整数,表示答案。

否则,输出 dottle bot

样例输入输出

样例输入 $1$
114514
样例输出 $1$
1
样例 $1$ 解释

删掉从左向右第三个位置上的 $4$ 后数字变为 $11514$,是一个 $3$ 的倍数。

样例输入 $2$
369
样例输出 $2$
0
样例 $2$ 解释

$369$ 是 $3$ 的倍数。

样例输入 $3$
11
样例输出 $3$
dottle bot
样例 $3$ 解释

注意不能擦掉所有数字,所以无解。

样例输入 $4$
283959283666555555
样例输出 $4$
2

数据范围

本题共 $10$ 个测试点,每个测试点 $10$ 分。对于所有测试点,保证 $1\leq n\leq 10^{18}$ 且 $n$ 的十进制表达中不含 $0$。

具体范围如下:

测试点编号 $n$ 特殊性质
$1\sim 2$ $\leq 9$
$3\sim 5$ $\leq 99$
$6$ $\leq 10^5$
$7\sim 9$ $\leq 10^{18}$ $n$ 的十进制表达长度为 $18$,且每一位在 $[1,9]$ 之间均匀随机
$10$