/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
英大文字のみからなる文字列 S が与えられます。
高橋君の目標は、S の文字のうちいくつかを置換することによって、S が ABC を部分文字列として含む個数をちょうど K 個 増やす ことです。
このようなことが可能か判定し、可能な場合は目標を達成するために高橋君が最低何文字置換する必要があるか求めてください。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
置換とは
S の文字のうちの 1 つを置換するとは、1\leq i\leq \lvert S\rvert をみたす整数 i を 1 つ選び、S の i 文字目を任意の英大文字 1 字 で置き換えることを指します。
ただし、\lvert S\rvert で S の長さを表すものとします。
部分文字列とは
S の部分文字列とは、S の先頭および末尾からそれぞれ 0 文字以上削除して得られる文字列のことを指します。
2 つの部分文字列は、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 個目のテストケースに対する答えを出力せよ。
ここで、各テストケースに対する答えとして、高橋君が目標を達成することが不可能な場合は -1 を、そうでない場合は目標を達成するために置換する必要のある文字の個数の最小値を出力せよ。
入力例 1
5 ATCABC 1 ABABC 1 XABCYZ 1 ZZZZZ 1 ABCBABCAEFCABAABC 2
出力例 1
1 -1 6 3 3
1 個目のテストケースにおいて、与えられる文字列 S=ATCABC は ABC を部分文字列として 1 つ含んでいます。
S の 2 文字目を B に置換すると、S=ABCABC となって、ABC を部分文字列として 2 つ含むようになります。
これにより、1 字置換することで、 ABC を部分文字列として含む個数が 1 つ増え、目標は達成されました。よって、1 行目には 1 を出力します。
2 個目のテストケースにおいて、与えられる文字列 S=ABABC は ABC を部分文字列として 1 つ含んでいますが、
S の文字をどのように置換しても、S が ABC を部分文字列として 2 つ含むようにすることはできません。
よって、2 行目には -1 を出力します。
3 個目のテストケースにおいて、与えられる文字列 S=XABCYZ は ABC を部分文字列として 1 つ含んでいます。
S が ABC を部分文字列として 2 つ含むようにするためには、S の全ての文字を置換し、S=ABCABC とする必要があります。
よって、3 行目には 6 を出力します。
Score : 500 points
Problem Statement
You are given a string S consisting of uppercase English letters.
Takahashi's goal is to increase the number of occurrences of ABC as a substring of S by exactly K, by replacing some characters of S.
Determine whether this is possible, and if so, find the minimum number of characters Takahashi needs to replace to achieve his goal.
T test cases are given; solve each one.
What does "replacing" mean?
Replacing one character of S means choosing an integer i satisfying 1\leq i\leq \lvert S\rvert and replacing the i-th character of S with any one uppercase English letter.
Here, \lvert S\rvert denotes the length of S.
What is a substring?
A substring of S is a string obtained by removing zero or more characters from the beginning and end of S.
Two substrings are counted as distinct if they are taken from different positions in S, even if they are equal as strings.
Constraints
- 1\leq T\leq 10^5
- S is a string of length between 3 and 3\times 10^5, inclusive, consisting of uppercase English letters.
- 1\leq K \leq 10
- In each input, the total length of S over all test cases is at most 3\times 10^5.
- T and K are integers.
Input
The input is given from Standard Input in the following format:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
\mathrm{case}_i represents the i-th test case.
Each test case is given in the following format:
S K
Output
Output T lines.
The i-th line (1\leq i\leq T) should contain the answer for the i-th test case.
For each test case, if it is impossible for Takahashi to achieve his goal, output -1; otherwise, output the minimum number of characters that need to be replaced to achieve his goal.
Sample Input 1
5 ATCABC 1 ABABC 1 XABCYZ 1 ZZZZZ 1 ABCBABCAEFCABAABC 2
Sample Output 1
1 -1 6 3 3
In the first test case, the given string S=ATCABC contains ABC as a substring once.
Replacing the second character of S with B gives S=ABCABC, which contains ABC as a substring twice.
Thus, replacing one character increases the number of occurrences of ABC as a substring by 1, achieving the goal. Therefore, output 1 on the first line.
In the second test case, the given string S=ABABC contains ABC as a substring once; no matter how the characters of S are replaced, it is impossible to make S contain ABC as a substring twice.
Therefore, output -1 on the second line.
In the third test case, the given string S=XABCYZ contains ABC as a substring once.
To make S contain ABC as a substring twice, all characters of S must be replaced, giving S=ABCABC.
Therefore, output 6 on the third line.