TITLE: Problem A. Bot Trust
#contents
#br
* 問題 [#f11c861b]
青とオレンジの色をした、フレンドリーなロボットがある。
意地悪なコンピューター管理者は、ロボットに試験を課すため、別の廊下でロボットを固定し、ケーキを与えていた。
各廊下には、番号k (1 ≦ k ≦ 100) が振られた、ボタンが100個設置されている。
ボタンkは、廊下の端からkメートル離れた所にあり、どちらのロボットも最初はボタン1の位置に置かれている。
ロボットは1秒の間に
- 左右どちらかに1メートル移動する
- その地点のボタンを押す
- 何もしない
のどれかをしなくてはいけない。
テストを完了するには、廊下に設置されたボタンを、決められた順番で押す必要がある。
幸い、ロボットはどのように押せばテストを達成できるか、その方法を知っている。
あなたには、ロボットがどれだけ少ない時間で、テストを完了することができるか計算して欲しい。
たとえば、ロボットが次のように行動するとする。
#pre{{
O 2, B 1, B 2, O 4
}}
ここで、「O 2」オレンジのロボットがボタン2を押すことを意味し、「B 1」は青のロボットがボタン1を押すことを意味する。
これを最短で行うと、次の表のように6秒で達成できる。
|経過時間|オレンジのロボット|青のロボット|h
|1|ボタン2へ移動する|ボタン1で停止する|
|2|ボタン2を押す|ボタン1で停止する|
|3|ボタン3へ移動する|ボタン1を押す|
|4|ボタン4へ移動する|ボタン2へ移動する|
|5|ボタン4で停止する|ボタン2を押す|
|6|ボタン4を押す|ボタン2で停止する|
上の例では、青のロボットがロボットがボタン2を押すまで、オレンジのロボットがボタン4を押せないことに注意すること。
* 入力 [#e0f3cc1d]
#pre{{
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回の繰り返しである。
* 出力 [#y6518ebe]
#pre{{
Case #x: y
...
}}
データセットごとに、データセットの番号x (1から開始する) と、ロボットがテストを完了する最短時間yを出力せよ。
* 制限 [#v5f53b53]
- 1 ≦ P ≦ 100
** データセット (小) [#u49deb00]
- 1 ≦ T ≦ 20
- 1 ≦ N ≦ 10
** データセット (大) [#id4e25c3]
- 1 ≦ T ≦ 100
- 1 ≦ N ≦ 100
* サンプル入出力 [#i6faac5b]
** 入力 [#kb32bdd6]
#pre{{
3
4 O 2 B 1 B 2 O 4
3 O 5 O 8 B 100
2 B 2 B 1
}}
** 出力 [#c6266166]
#pre{{
Case #1: 6
Case #2: 100
Case #3: 4
}}
* ヒント [#je37cc35]
#region
ロボットの動きをシミュレートするだけ。
必ずロボットは、次に押すボタンに向けて動く。
#endregion
#br
* 提出・原文 [#vd061f61]
http://code.google.com/codejam/contest/dashboard?c=975485#s=p0
#br
* 回答例 [#e603a7ea]
|作成者|ソースコード|
|&areaedit(){pine};|&attachref(./GCJ_2011QRA_BotTrust.cpp);|
[&addline(file,above){入力欄を追加};]
#br
-----
#pcomment