← 返回题目列表

Codeforces · 2156/B

B. 奇怪的机器

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

你有 $$$n$$$ 机器排列成一个圆圈,其中 $$$n$$$ 最多为 $$$20$$$。每台机器都是以下类型之一 A 或输入 B。机器从 $$$1$$$ 到 $$$n$$$ 顺时针编号,第 $$$i$$$ 机器的类型用 $$$s_i$$$ 表示。每台机器都接受一个整数 $$$x$$$ 并根据其类型更新它:

  • 类型 A:将 $$$x$$$ 减少 $$$1$$$。正式地,更新 $$$x := x - 1$$$。
  • 类型 B:将 $$$x$$$ 替换为其一半值的下限。形式上,更新$$$x := \left\lfloor\frac{x}{2}\right\rfloor$$$,其中$$$\lfloor y\rfloor$$$表示$$$y$$$的下限,它是小于或等于$$$y$$$的最大整数。

您将收到 $$$q$$$ 查询,每个查询由一个整数 $$$a$$$ 组成。在每个查询中,您从机器 $$$1$$$ 开始,保存一个整数 $$$a$$$。每一秒,以下两个动作按顺序发生:

  1. 当前机器根据其类型更新$$$a$$$。
  2. 然后,顺时针移动一步到下一台机器。正式地
    • 如果您在 $$$i$$$ 机器上,其中 $$$1 \le i \le n - 1$$$,请移至机器 $$$i + 1$$$。
    • 如果您在机器$$$n$$$,请移至机器$$$1$$$。

此过程将继续,直到您的整数 $$$a$$$ 变为 $$$0$$$。对于每个查询,确定 $$$a$$$ 到达 $$$0$$$ 所需的秒数。

请注意,所有查询都是相互独立的。

输入

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

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1\le n\le 20$$$, $$$1\le q\le 10^4$$$) - 分别是机器数量和查询数量。

每个测试用例的第二行包含一个字符串 $$$s$$$ ($$$|s| = n$$$ 和 $$$s_i = \mathtt{A} \text{ 或 }\mathtt{B}$$$)——机器的类型。

每个测试用例的第三行包含 $$$q$$$ 整数 $$$a_1, a_2, \ldots, a_q$$$ ($$$1\le a_i\le 10^9$$$) - 每个查询的初始整数。

请注意,所有测试用例的 $$$n$$$ 总和没有限制。

保证所有测试用例的$$$q$$$总和不超过$$$10^4$$$。

输出

对于每个测试用例,输出 $$$q$$$ 整数,表示每个查询的答案。

示例

输入
复制

3
2 2
BA
3 4
1 1
B
20
6 4
BAABBA
2 8 32 95

输出
复制

2
3
5
2
5
8
11

注意

在第一个测试用例中,查询如下:

  • 查询 $$$1$$$: $$$a = 3$$$
    1. 从机器 $$$1$$$ 开始。机器 $$$1$$$ 将 $$$a$$$ 替换为其价值一半的下限。现在,$$$a = \left\lfloor\frac{3}{2}\right\rfloor = 1$$$。
    2. 移动到机器$​​$$2$$$。机器 $$$2$$$ 将 $$$a$$$ 减少 $$$1$$$。现在,$$$a = 1 - 1 = 0$$$。
    因此,$$$a$$$ 需要 $$$2$$$ 秒才能达到 $$$0$$$。
  • 查询 $$$2$$$: $$$a = 4$$$
    1. 从机器 $$$1$$$ 开始。机器 $$$1$$$ 将 $$$a$$$ 替换为其价值一半的下限。现在,$$$a = \left\lfloor\frac{4}{2}\right\rfloor = 2$$$。
    2. 移动到机器$​​$$2$$$。机器 $$$2$$$ 将 $$$a$$$ 减少 $$$1$$$。现在,$$$a = 2 - 1 = 1$$$。
    3. 移回机器$$$1$$$。机器 $$$1$$$ 将 $$$a$$$ 替换为其价值一半的下限。现在,$$$a = \left\lfloor\frac{1}{2}\right\rfloor = 0$$$。
    因此,$$$a$$$ 需要 $$$3$$$ 秒才能达到 $$$0$$$。

在第二个测试用例中,只有一个 $$$a = 20$$$ 的查询:

  1. 从机器 $$$1$$$ 开始。机器 $$$1$$$ 将 $$$a$$$ 替换为其价值一半的下限。现在,$$$a = \left\lfloor\frac{20}{2}\right\rfloor = 10$$$。
  2. 移动到机器$​​$$1$$$。机器 $$$1$$$ 将 $$$a$$$ 替换为其价值一半的下限。现在,$$$a = \left\lfloor\frac{10}{2}\right\rfloor = 5$$$。
  3. 移动到机器$​​$$1$$$。机器 $$$1$$$ 将 $$$a$$$ 替换为其价值一半的下限。现在,$$$a = \left\lfloor\frac{5}{2}\right\rfloor = 2$$$。
  4. 移动到机器$​​$$1$$$。机器 $$$1$$$ 将 $$$a$$$ 替换为其价值一半的下限。现在,$$$a = \left\lfloor\frac{2}{2}\right\rfloor = 1$$$。
  5. 移动到机器$​​$$1$$$。机器 $$$1$$$ 将 $$$a$$$ 替换为其价值一半的下限。现在,$$$a = \left\lfloor\frac{1}{2}\right\rfloor = 0$$$。

因此,$$$a$$$ 需要 $$$5$$$ 秒才能达到 $$$0$$$。