Google Code Jam Qualification Round - A問題「Bot Trust」

Dashboard - Qualification Round 2011 - Google Code Jam

問題

BlueとOrangeのロボットが2本の半直線上にあり、それぞれ半直線上を動けるようになっている。

それぞれの半直線上には100個のボタンがあり、それぞれに「1, 2, ..., 100」とラベルが付いている。
ボタンkは原点からkメートルの所にあり、最初に2体のロボットはボタン1にいる。
1秒ごとに、ロボットは「どちらかの方向に1メートル進む」「ボタンを押す」「その場に居座る」の3種類の動作のいずれかが可能である。
ロボットは指定された順序で指定されたボタンを押さなければならない。
ロボットはそれぞれのボタンがどこにあるかを知っているとして、
さて、指定された全てのボタンを最短時間で押し終えるには何秒かかるだろうか?

例えば、下記の指示があったとする。

    O 2, B 1, B 2, O 4

「O 2」は「Orangeロボットがボタン2を押す」ことを意味し、「B 1」は「Blueロボットがボタン1を押す」ことを意味する。

この指示において、ロボットは下記の手順で6秒で全てのボタンを押し終えることができる。

Time | Orange           | Blue
-----+------------------+-----------------
  1  | Move to button 2 | Stay at button 1
  2  | Push button 2    | Stay at button 1
  3  | Move to button 3 | Push button 1
  4  | Move to button 4 | Move to button 2
  5  | Stay at button 4 | Push button 2
  6  | Push button 4    | Stay at button 2

注意) Blueロボットは、Orangeロボットが「O 2」を完了させる(ボタン2を押し終える)まで、「B 1」(ボタン1を押す)のを待っている。

入力

最初の1行はテストケースの数Tを表し、後にT個のテストケースが続く。

それぞれのテストケースは1行で表され、押されるべきボタンの総数である非負整数Nが最初に書かれている。
Nに続いてN個の「Ri Pi」が書かれており、Riはロボットの色("O" or "B")、Piはボタンの番号となっている。

出力

それぞれのテストケースにおいて、"Case #x: y" の形式で1行ずつ結果を出力する。
xはテストケース番号(1から始まる)で、yはロボットが全てのボタンを押し終えるまでの最短時間の秒数である。

制限

1 ≦ Pi ≦ 100 for all i.

Small dataset

1 ≦ T ≦ 20.
1 ≦ N ≦ 10.

Large dataset

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


所感
仮に1秒ごとのロボットの動きをエミュレートしたとしても、毎回ロボットがボタン1〜100をせわしなく動いたとして 100 * N * T = 100万秒分のエミュレートをすれば解けるので、そんなに工夫しなくても良い易しい問題だと思います。


プログラミングコンテストチャレンジブック

プログラミングコンテストチャレンジブック