← 返回题目列表

AtCoder · arc169_e

E. 避免无聊的比赛

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

分数: 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