Below is the description of a problem called 'Bot Trust', from 'Google Code Jam - 2011':

Problem

-------

Blue and Orange are friendly robots. An evil computer mastermind has locked them up in separate hallways to test them, and then possibly give them cake.

Each hallway contains 100 buttons labeled with the positive integers {1, 2, ..., 100}. Button k is always k meters from the start of the hallway, and the robots both begin at button 1. Over the period of one second, a robot can walk one meter in either direction, or it can press the button at its position once, or it can stay at its position and not press the button. To complete the test, the robots need to push a certain sequence of buttons in a certain order. Both robots know the full sequence in advance. How fast can they complete it?

For example, let's consider the following button sequence:

O 2, B 1, B 2, O 4

Here, O 2 means button 2 in Orange's hallway, B 1 means button 1 in Blue's hallway, and so on. The robots can push this sequence of buttons in 6 seconds using the strategy shown below:

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

Note that Blue has to wait until Orange has completely finished pushing O 2 before it can start pushing B 1.

Input

-----

The first line of the input gives the number of test cases, T. T test cases follow.

Each test case consists of a single line beginning with a positive integer N, representing the number of buttons that need to be pressed. This is followed by N terms of the form "Ri Pi" where Ri is a robot color (always 'O' or 'B'), and Pi is a button position.

Output

------

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the minimum number of seconds required for the robots to push the given buttons, in order.

Limits

------

1 ≤ Pi ≤ 100 for all i.

Small dataset

-------------

1 ≤ T ≤ 20.

1 ≤ N ≤ 10.

Large dataset

-------------

1 ≤ T ≤ 100.

1 ≤ N ≤ 100.

Sample Input

------------

3

4 O 2 B 1 B 2 O 4

3 O 5 O 8 B 100

2 B 2 B 1

Output

------

Case #1: 6

Case #2: 100

Case #3: 4

The solution to the problem can be easily coded, after understanding the fact that the robot (which was not scheduled to press the switch) can freely move to it's destination (next switch), so as to make the time required to solve the problem, as minimal as possible. Both the robots start at 1. So, for example, if one robot has to press the switch at 10 (first move), it takes 9 seconds (10 - 1) to move and 1 to press the switch...So, it takes a total of 10 seconds...In these 10 seconds, the other robot can move as long as possible and stay-put there, waiting for its turn. I used Java datastructures 'Queue' and 'Deque' to solve the problem.

Below is my solution, in Java:

- GCJ 2014 - 'Deceitful War'
- GCJ 2014 - 'Cookie Clicker Alpha' Problem
- GCJ 2014 - Magic Trick
- GCJ 2013 - Fair And Square
- GCJ 2013 - Tic-Tac-Toe-Tomek
- GCJ 2012 - Recycled Numbers
- GCJ 2012 - Dancing With Googlers
- GCJ 2012 - Speaking In Tongues
- GCJ 2011 - Magicka
- GCJ 2011 - Bot Trust
- GCJ 2010 - Fair Warning
- GCJ 2010 - Snapper Chain
- Odd Man Out - GCJ 2010 (Africa)
- Store Credit - GCJ 2010 (Africa)
- T9Spelling - GCJ 2010 (Africa)
- Reverse Words - GCJ 2010 (Africa)
- All Your Base - GCJ 2009
- Alien Language - GCJ 2009
- Google Code Jam 2008 - Minimum Scalar Product
- GCJ 2008 - Alien Numbers
- Playing With Googol
- Google Billboard Puzzle
- Euler's Number (e) to 10000 digits
- Spiral Walking

- GCJ 2014 - 'Deceitful War'
- GCJ 2014 - 'Cookie Clicker Alpha' Problem
- GCJ 2014 - Magic Trick
- GCJ 2013 - Fair And Square
- GCJ 2013 - Tic-Tac-Toe-Tomek
- GCJ 2012 - Recycled Numbers
- GCJ 2012 - Dancing With Googlers
- GCJ 2012 - Speaking In Tongues
- GCJ 2011 - Magicka
- GCJ 2011 - Bot Trust
- GCJ 2010 - Fair Warning
- GCJ 2010 - Snapper Chain
- Odd Man Out - GCJ 2010 (Africa)
- Store Credit - GCJ 2010 (Africa)
- T9Spelling - GCJ 2010 (Africa)
- Reverse Words - GCJ 2010 (Africa)
- All Your Base - GCJ 2009
- Alien Language - GCJ 2009
- Google Code Jam 2008 - Minimum Scalar Product
- GCJ 2008 - Alien Numbers
- Playing With Googol
- Google Billboard Puzzle
- Euler's Number (e) to 10000 digits
- Spiral Walking

- Recursion Depth - Java
- RESTFul Web Service - Seam Component Injection
- Micro-benchmarking Java Code With Caliper
- JSF & Highcharts (Javascript Chart Library)
- Add 'Syntactic Sugar' With 'Fluent Interface'
- Priority Queue in Java
- Compile Java Files At Runtime
- Missing Number
- Guice - AOP (Aspect Oriented Programming)
- Creating Executable Jar File With Maven Shade Plugin
- Java - Looping Through A Range of BigInteger Values
- Create Your Own Dependency Injection Framework
- Google Guice - Example
- Guice Grapher - Example
- Using Richfaces 'Suggestion Box' As Combo Box
- Hashcode Of A String In Java
- Richfaces - Modal Panel As A Wizard
- Jasper Reports - Thermometer Report
- Jasper Reports - Gantt Chart
- Jasper Reports - Example
- Seam - Load i18n Messages From Database
- Autoboxing In Java & Bug Patterns
- Dont Smack The Stack (Deal With Stack Overflow Exceptions)

The views expressed on this blog are my personal views and do not reflect the views of
my employer or campaigns I am supporting.

All sample code is provided for illustrative purposes only. These examples have not been thoroughly tested under all conditions. The writer therefore, cannot guarantee or imply reliability, serviceability, or function of these programs.

All programs contained herein are provided to you "AS IS" without any warranties of any kind. The implied warranties of non-infringement, merchantability and fitness for a particular purpose are expressly disclaimed.

All sample code is provided for illustrative purposes only. These examples have not been thoroughly tested under all conditions. The writer therefore, cannot guarantee or imply reliability, serviceability, or function of these programs.

All programs contained herein are provided to you "AS IS" without any warranties of any kind. The implied warranties of non-infringement, merchantability and fitness for a particular purpose are expressly disclaimed.