← 返回题目列表

Codeforces · 1898/A

A. 米莉卡和字符串

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

Milica 有一个长度为 $$$n$$$ 的字符串 $$$s$$$,仅包含字符 A 和 B。她想要修改 $$$s$$$,使其恰好包含 B 的 $$$k$$$ 实例。在一个操作中,她可以执行以下操作:

- 选择一个整数 $$$i$$$ ($$$1 \leq i \leq n$$$) 和一个字符 $$$c$$$ ($$$c$$$ 等于 A 或 B)。
- 然后,将字符串 $$$s$$$ 的前 $$$i$$$ 字符(即字符 $$$s_1、s_2、\ldots、s_i$$$)替换为 $$$c$$$。

Milica 不想执行太多操作,以免浪费太多时间。

她要求你找出修改 $$$s$$$ 所需的最少操作数,使其恰好包含 B 的 $$$k$$$ 个实例。她还希望你找到这些操作(即在每个操作中选择的整数 $$$i$$$ 和字符 $$$c$$$)。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \leq t \leq 500$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$3 \leq n \leq 100$$$, $$$0 \leq k \leq n$$$) - 字符串 $$$s$$$ 的长度以及 B Milica 最后希望出现在 $$$s$$$ 中的字符数。

每个测试用例的第二行包含长度为$$$n$$$的字符串$$$s$$$,仅由字符A和B组成。

输出

对于每个测试用例,在第一行输出一个整数 $$$m$$$ — Milica 应该执行的最小操作数。

在接下来的 $$$m$$$ 行的第 $$$j$$$ 行中,输出一个整数 $$$i$$$ ($$$1 \le i \le n$$$) 和一个字符 $$$c$$$ ($$$c$$$ 是 'A' 或 'B') – 第 $$$j$$$ 操作的参数,如语句中所述。

如果存在多个具有最少可能运算次数的解,则输出其中任何一个。

示例

输入 #1

5
5 2
AAABB
5 3
AABAB
5 0
BBBBB
3 0
BAA
10 3
BBBABBBBAB

输出 #1

0
1
1 B
1
5 A
1
2 A
1
6 A

注意

在第一个测试用例中,$$$s$$$ 中已经有 $$$2$$$ 字符 B,因此 Milica 不必执行任何操作。

在第二个测试用例中,在一次操作中在 $$$s$$$ 中实现 $$$3$$$ 字符 B 的唯一方法是在第一个操作中用 B 替换 $$$s$$$ 的第一个字符:AABAB $$$\rightarrow$$$ BABAB。

在第三个测试用例中,在一次操作中在 $$$s$$$ 中实现 $$$0$$$ 字符 B 的唯一方法是在第一个操作中将 $$$s$$$ 的前 $$$5$$$ 字符替换为 A:BBBBB $$$\rightarrow$$$ AAAAA。

在第四个测试用例中,在一次操作中实现 $$$s$$$ 中的 $$$0$$$ 字符 B 的方法之一是在第一次操作中将 $$$s$$$ 的前 $$$2$$$ 字符替换为 A:BAA $$$\rightarrow$$$ AAA。请注意,“1 A”和“3 A”也是正确的一次操作解决方案。