Problem A. Bot Trust

問題

青とオレンジの色をした、フレンドリーなロボットがある。
意地悪なコンピューター管理者は、ロボットに試験を課すため、別の廊下でロボットを固定し、ケーキを与えていた。

各廊下には、番号k (1 ≦ k ≦ 100) が振られた、ボタンが100個設置されている。
ボタンkは、廊下の端からkメートル離れた所にあり、どちらのロボットも最初はボタン1の位置に置かれている。

ロボットは1秒の間に

• 左右どちらかに1メートル移動する
• その地点のボタンを押す
• 何もしない

のどれかをしなくてはいけない。

テストを完了するには、廊下に設置されたボタンを、決められた順番で押す必要がある。
幸い、ロボットはどのように押せばテストを達成できるか、その方法を知っている。

あなたには、ロボットがどれだけ少ない時間で、テストを完了することができるか計算して欲しい。

たとえば、ロボットが次のように行動するとする。

O 2, B 1, B 2, O 4

ここで、「O 2」オレンジのロボットがボタン2を押すことを意味し、「B 1」は青のロボットがボタン1を押すことを意味する。

これを最短で行うと、次の表のように6秒で達成できる。

上の例では、青のロボットがロボットがボタン2を押すまで、オレンジのロボットがボタン4を押せないことに注意すること。

入力

T
N R1 P1 R2 P2 ... RN PN
N R1 P1 R2 P2 ... RN PN
...

1行目に、データセットの個数Tが与えられる。
2行目から(T+1)行目に、T個のデータセットが与えられる。

一つのデータセットは、1行で構成され、押さないといけないボタンの個数N、ロボットの色R (O もしくは B)、及びボタンの番号PのN回の繰り返しである。

出力

Case #x: y
...

データセットごとに、データセットの番号x (1から開始する) と、ロボットがテストを完了する最短時間yを出力せよ。

制限

• 1 ≦ P ≦ 100

データセット (小)

• 1 ≦ T ≦ 20
• 1 ≦ N ≦ 10

データセット (大)

• 1 ≦ T ≦ 100
• 1 ≦ N ≦ 100

サンプル入出力

入力

3
4 O 2 B 1 B 2 O 4
3 O 5 O 8 B 100
2 B 2 B 1

出力

Case #1: 6
Case #2: 100
Case #3: 4

ヒント

提出・原文

http://code.google.com/codejam/contest/dashboard?c=975485#s=p0

回答例

作成者	ソースコード
pine[e]	GCJ_2011QRA_BotTrust.cpp

[入力欄を追加]