← 返回题目列表

Codeforces · 779/B

B. 奇怪的四舍五入

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

波利卡普对整数很着迷。他特别喜欢能被10k整除的数字。

在给定的 n 个数字中,Polycarp 想要删除最少数量的数字以获得可被 10k 整除的数字。例如,如果 k = 3,则在数字 30020 中删除一个数字 (2) 就足够了。在本例中,结果为 3000,可被 103 整除 = 1000。

编写一个程序,打印给定整数 n 中要删除的最小位数,使得结果能被 10k 整除。结果不应以不必要的前导零开头(即,零只能以数字 0 开头,要求精确地写为一位数)。

保证答案存在。

输入

输入的唯一行包含两个整数 n 和 k (0 ≤ n ≤ 2 000 000 000, 1 ≤ k ≤ 9)。

保证答案存在。输入中的所有数字均以传统的整数表示法编写,即没有任何额外的前导零。

输出

打印 w — 需要擦除的最少位数。从数字 n 中删除适当的 w 位后,结果应该具有可被 10k 整除的值。在单一情况下,结果可以从数字 0 开始(结果为零,并且恰好由唯一的数字 0 写入)。

示例

输入 #1

30020 3

输出 #1

1

输入 #2

100 9

输出 #2

2

输入 #3

10203049 2

输出 #3

3

注意

在示例 2 中,您可以删除两个数字:1 和任何 0。结果是数字 0,它可以被任何数字整除。