E - Avoid Boring Matches Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 900 点

問題文

1 から 2^N までの番号のついた 2^N 人の参加者がいる大会があります．

大会は次のように進行します．

  • まず最初に，それぞれの参加者に赤または青の帽子をかぶせる． ここで，各参加者にかぶせる帽子の色は文字列 S によって与えられる． 具体的には，S の i 文字目 (1 \leq i \leq 2^N) が R のときは赤い帽子を，B のときは青い帽子を参加者 i にかぶせる．

  • その後，参加者が 1 人になるまで以下の操作を繰り返す．

    • 現在の参加者の人数を 2k 人とする．参加者を k 個の 2 人組に分ける． この組分けはあなたが自由に選ぶことができる． そしてそれぞれの組で試合を行い，勝者は残り，敗者は大会から去る． なお，参加者は強さ順に番号づけられているため，必ず番号の小さい参加者が勝利する．

あなたは，赤い帽子をかぶった参加者同士の試合をつまらない試合と呼んでいます． あなたの目標は，大会中につまらない試合が発生しないように各組分けを行うことです．

目標が達成可能であるか否かは文字列 S に依存します． そこであなたは，大会の開始前に S に細工することにしました． 具体的には，あなたは次の操作を 0 回以上行えます．

  • S 中の隣接する 2 文字を選び，入れ替える．

操作の結果目標を達成することが可能かどうか判定してください． また，可能な場合は必要な最小の操作回数を求めてください．

制約

  • 1 \leq N \leq 18
  • S は R, B からなる長さ 2^N の文字列．
  • 入力される値はすべて整数．

入力

入力は以下の形式で標準入力から与えられる．

N
S

出力

目標を達成することが不可能な場合は -1 を出力せよ． 可能な場合は必要な最小の操作回数を出力せよ．

入力例 1

2
RRBB

出力例 1

1

操作を 1 回も行わないと，目標を達成することができません．

S の 2 文字目と 3 文字目を入れ替える操作を行い，S=RBRB とすると，以下のようにして目標を達成できます．

  • 参加者 1,2,3,4 にそれぞれ 赤,青,赤,青 の帽子をかぶせる．
  • 4 人の参加者を 2 つの組 (1,4),(2,3) に分ける． ここでつまらない試合は発生しない． 試合の結果，参加者 1,2 が勝ち残る．
  • 2 人の参加者を 1 つの組 (1,2) に分ける． ここでつまらない試合は発生しない． 試合の結果，参加者 1 が勝ち残る．

よって答えは 1 です．

入力例 2

1
RR

出力例 2

-1

入力例 3

4
RBBRRBRBBRBBBRBR

出力例 3

0

入力例 4

5
RBRRBRRRBRRRRRRRRRBBBBBBBBBBBBBB

出力例 4

11

Score : 900 points

Problem Statement

There is a tournament with 2^N participants, numbered 1 to 2^N.

The tournament proceeds as follows:

  • First, each participant is given a red or blue hat. You are given the color of the hat for each participant as the string S. Specifically, participant i is given a red hat if the i-th character (1 \leq i \leq 2^N) of S is R, and a blue hat if it is B.

  • Then, the following operation is repeated until there is only one participant remaining:

    • Let 2k be the current number of participants. Divide the participants into k pairs. You can freely choose how to pair them. Then, a match is held for each pair; the winner remains, and the loser leaves the tournament. The participants are numbered in descending order of strength, so the participant with the smaller number always wins.

A match between two participants wearing red hats is called a boring match. Your goal is to arrange the pairings so that no boring matches occur during the tournament.

Whether the goal is achievable or not depends on the string S. Hence, you have decided to tamper with S before the start of the tournament. Specifically, you can perform the following operation zero or more times:

  • Choose two adjacent characters in S and swap them.

Determine whether it is possible to achieve the goal after operations. If it is, find the minimum number of operations required.

Constraints

  • 1 \leq N \leq 18
  • S is a string of length 2^N consisting of R and B.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
S

Output

If it is impossible to achieve the goal, print -1. Otherwise, print the minimum number of operations required.

Sample Input 1

2
RRBB

Sample Output 1

1

Without performing any operations, you cannot achieve the goal.

If you swap the second and third characters of S, making S=RBRB, you can achieve the goal as follows:

  • Give red, blue, red, and blue hats to participants 1, 2, 3, and 4, respectively.
  • Divide the four participants into two pairs (1,4),(2,3). No boring matches occur here. After the matches, participants 1 and 2 remain.
  • Divide the two participants into one pair (1,2). No boring matches occur here. After the match, participant 1 remains.

Therefore, the answer is 1.

Sample Input 2

1
RR

Sample Output 2

-1

Sample Input 3

4
RBBRRBRBBRBBBRBR

Sample Output 3

0

Sample Input 4

5
RBRRBRRRBRRRRRRRRRBBBBBBBBBBBBBB

Sample Output 4

11