← 返回题目列表

AtCoder · abc462_f

F. 更多ABC

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

分数: 500 点

问题陈述

给你一个字符串 S 由大写英文字母组成。
高桥的目标是 增加 出现的次数 ABC 作为子串 S 正是 K,通过替换一些字符 S.

确定这是否可能,如果可以,找到高桥需要替换的最少字符数才能实现他的目标。

T 给出了测试用例;逐一解决。

“替换”是什么意思?

替换 1 个字符 S 表示选择一个整数 i 满意 1\leq i\leq \lvert S\rvert 并替换 i- 第一个字符 S 与任何 一 大写英文字母。
在这里, \lvert S\rvert 表示长度 S.

什么是子串?

的子串 S 是从开头和结尾删除零个或多个字符得到的字符串 S.
如果两个子字符串取自不同位置,则它们被视为不同的子字符串 S,即使它们作为字符串相等。

约束

  • 1\leq T\leq 10^5
  • S 是长度介于 3 和 3\times 10^5,包含在内,由大写英文字母组成。
  • 1\leq K \leq 10
  • 在每个输入中,总长度 S 所有测试用例最多 3\times 10^5.
  • T 和 K 是整数。

输入

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

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

\mathrm{case}_i 代表 i- 第一个测试用例。
每个测试用例均按以下格式给出:

S
K

输出

输出 T 行。
的 i第行 (1\leq i\leq T) 应包含以下问题的答案 i- 第一个测试用例。
对于每个测试用例,如果 Takahashi 不可能实现他的目标,则输出 -1;否则,输出达到他的目标需要替换的最少字符数。


示例输入 1

5
ATCABC
1
ABABC
1
XABCYZ
1
ZZZZZ
1
ABCBABCAEFCABAABC
2

示例输出 1

1
-1
6
3
3

在第一个测试用例中,给定的字符串 S=ATCABC 包含 ABC 作为子字符串一次。
替换第二个字符 S 与 B 给出 S=ABCABC,其中包含 ABC 作为子字符串两次。
因此,替换一个字符会增加出现的次数 ABC 作为子字符串 1,实现目标。因此,输出 1 在第一行。

在第二个测试用例中,给定的字符串 S=ABABC 包含 ABC 作为子字符串一次;无论角色如何 S 被替换,这是不可能的 S 包含 ABC 作为子字符串两次。
因此,输出 -1 在第二行。

在第三个测试用例中,给定的字符串 S=XABCYZ 包含 ABC 作为子字符串一次。
使 S 包含 ABC 作为子字符串两次,所有字符 S 必须更换,给予 S=ABCABC.
因此,输出 6 在第三行。