分数: 900 点
问题陈述
有一场锦标赛 2^N 参与者,编号 1 to 2^N.
比赛进行如下:
-
首先,每个参与者都会获得一顶红色或蓝色的帽子。 您将获得每个参与者帽子的颜色作为字符串 S。 具体来说,参与者 i 被给予红帽,如果 i- 第一个字符 (1 \leq i \leq 2^N)的 S is
R,如果是的话,还有一顶蓝色帽子B. -
然后,重复以下操作,直到只剩下一名参与者:
- 让 2k 是当前参与者的数量。将参与者分为 k 对。 您可以自由选择如何配对它们。 然后,每对进行一场比赛;获胜者保留,失败者退出比赛。 参赛者按强度降序编号,因此具有 较小 数字总是获胜。
两名戴红帽子的参赛者之间的比赛称为一场比赛 无聊 匹配。 您的目标是安排配对,以便锦标赛期间不会发生无聊的比赛。
目标能否实现取决于字符串 S。 因此,你决定篡改 S 比赛开始前。 具体来说,您可以执行以下操作零次或多次:
- 选择两个相邻的字符 S 并交换它们。
判断运营后能否达到目标。 如果是,求所需的最少操作次数。
约束
- 1 \leq N \leq 18
- S 是一个长度为的字符串 2^N 组成
R和B. - 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N S
输出
如果无法实现目标,则打印 -1。 否则,打印所需的最少操作数。
样本输入 1
2 RRBB
示例输出 1
1
如果不执行任何操作,则无法实现目标。
如果交换第二个和第三个字符 S, 制作 S=RBRB,您可以通过以下方式实现目标:
- 给参与者红色、蓝色、红色和蓝色的帽子 1, 2, 3,和 4。
- 将四名参与者分成两对 (1,4),(2,3)。 这里不会发生无聊的比赛。 比赛结束后,参赛者 1 和 2 保留。
- 将两个参与者分成一对 (1,2)。 这里不会发生无聊的比赛。 比赛结束后,参赛者 1 仍然存在。
因此,答案是 1.
示例输入 2
1 RR
示例输出 2
-1
示例输入 3
4 RBBRRBRBBRBBBRBR
示例输出 3
0
示例输入 4
5 RBRRBRRRBRRRRRRRRRBBBBBBBBBBBBBB
示例输出 4
11