← 返回题目列表

Codeforces · 1400/F

F. x 素数子串

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

给定一个整数值 $$$x$$$ 和一个字符串 $$$s$$$,其中包含从 $$$1$$$ 到 $$$9$$$ 的数字。

字符串的子字符串是该字符串的连续子序列。

令 $$$f(l, r)$$$ 为子串 $$$s[l..r]$$$ 的数字之和。

让我们调用子字符串 $$$s[l_1..r_1]$$$ $$$x$$$-prime if

- $$$f(l_1, r_1) = x$$$;
- 没有值 $$$l_2, r_2$$$ 使得 $$$l_1 \le l_2 \le r_2 \le r_1$$$; $$$f(l_2, r_2) \neq x$$$; $$$x$$$ 可以被 $$$f(l_2, r_2)$$$ 整除。

您可以从字符串中删除一些字符。如果删除一个字符,则字符串的两个结果部分将连接起来,而不更改其顺序。

您应该从字符串中删除最少多少个字符,以便其中不存在 $$$x$$$ 素数子字符串?如果给定字符串 $$$s$$$ 中不存在 $$$x$$$ 素数子字符串,则打印 $$$0$$$。

输入

第一行包含字符串 $$$s$$$ ($$$1 \le |s| \le 1000$$$)。 $$$s$$$ 仅包含从 $$$1$$$ 到 $$$9$$$ 的数字(含)。

第二行包含一个整数 $$$x$$$ ($$$1 \le x \le 20$$$)。

输出

打印单个整数 - 应从字符串中删除的最小字符数,以便其中不存在 $$$x$$$ 素数子字符串。如果给定字符串 $$$s$$$ 中不存在 $$$x$$$ 素数子字符串,则打印 $$$0$$$。

示例

输入 #1

116285317
8

输出 #1

2

输入 #2

314159265359
1

输出 #2

2

输入 #3

13
13

输出 #3

0

输入#4

3434343434
7

输出#4

5

注意

在第一个示例中,有两个 $$$8$$$ 素数子字符串“8”和“53”。您可以擦除这些字符以删除这两个字符:“116285317”。生成的字符串“1162317”不包含 $$$8$$$ 素数子字符串。删除这些字符也是一个有效的答案:“116285317”。

在第二个示例中,您只需删除两个即可。

在第三个示例中,没有 $$$13$$$-素数子字符串。根本不存在数字总和等于 $$$13$$$ 的子字符串。

在第四个示例中,字符串中既不能包含“34”,也不能包含“43”。因此,你必须要么全部删除,要么全部删除。每个都有$$$5$$$,所以哪个并不重要。