Jolly Jumpers..~

Problem Statement
     
A string of letters A, B, C is forbidden if there are three consecutive letters from which one is A, one is B, and one is C. For example, BAACAACCBAAA is forbidden, while AABBCCAABB is not.  Your task is to calculate how many such strings of length n are not forbidden.
Definition
   
Class:
ForbiddenStrings
Method:
countNotForbidden
Parameters:
int
Returns:
long long
Method signature:
long long countNotForbidden(int n)
(be sure your method is public)
   
 
Constraints
-
n will be between 1 and 30, inclusive.
Examples
0)
 
   
2
Returns: 9
All 9 strings of length 2 are not forbidden.
1)
 
   
3
Returns: 21
There are 27 strings of length 3. Of these, 6 contain one occurrence of each letter. Those 6 strings are forbidden, so you should return 21.
2)
 
   
4
Returns: 51
 
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

Problem Statement
     
Tablature is a popular way of notating songs played on fretted string instruments. Each line represents a string, and numbers written on the lines tell you which frets to press down when playing those strings. Here is an example: 
------------
-3----------
-------0----
---2--------
-------0----
------------
The top line is the first string, the line below that is the second string, and so on. Tablature is read from left to right, and the i-th column represents the notes played at time i. In this example, there are no numbers in column 0, so this means that nothing is played at time 0. At time 1, a note is played by holding down the 3rd fret of the second string and plucking that string. At time 3, a note is played on the 2nd fret of the fourth string. Finally, at time 7, there are two notes played simultaneously as a chord. The number 0 means that you should pluck a string without holding down a fret. This is called an open string. In this example, you play the open third and fifth strings simultaneously.  Each open string may have a different pitch (i.e. may produce a higher or lower sound). For example, in standard guitar tuning, the pitch of the first string is 5 semitones higher than the second string. When you hold down the n-th fret (where 1 is the first fret) while playing a string, the resulting pitch is n semitones higher than that open string's pitch.  You are given a vector <string> tab containing the tablature for a song played on some instrument A (a guitar, for example). However, you want to play it on a different instrument B (maybe a mandolin, for example). You know the pitches of the open strings on each instrument, and they are given in the vector <int>s stringsA and stringsB. The i-th element of each vector <int> represents the pitch of the i-th string, and is given as the number of semitones above some base pitch 0. Both instrument A and instrument B have 35 frets. Frets numbered 10 through 35 are represented by the uppercase letters 'A' to 'Z'.  Your task is to write a program that will automatically transform the original tablature so it can be played on instrument B. Since different instruments have different ranges, you may also want to transpose the song to a different key. For this, you are given an int d, and you must increase the pitch of every note by d semitones (d can be negative, so you may end up lowering the pitches). Note that it is possible for different strings to play the same exact pitch at the same time in the original song. When that happens, the transformed tablature must also play that sound the same number of times as in the original version.  Sometimes there will be multiple ways to play a note on instrument B. In such cases, choose the string with the highest open pitch that can play that note. If there are multiple such strings, choose the bottom-most one among them (strings are listed from top to bottom). For chords, apply that same rule to each individual note in the chord. You must assign the notes in order, starting with the note that has the highest pitch, then the note with the second-highest pitch, and so on. You can only play a single note on each string, so only consider unused strings when assigning the notes of a chord. If you are unable to find a valid way to play a note or chord on instrument B using these rules, fill the entire column with lowercase 'x' characters instead. Return a vector <string> containing the transformed tablature for instrument B.
Definition
   
Class:
StringsAndTabs
Method:
transformTab
Parameters:
vector <string>, vector <int>, vector <int>, int
Returns:
vector <string>
Method signature:
vector <string> transformTab(vector <string> tab, vector <int> stringsA, vector <int> stringsB, int d)
(be sure your method is public)
   
 
Notes
-
The input tablature tab is not necessarily created using the rules given.
Constraints
-
tab will contain between 1 and 50 elements, inclusive.
-
Each element of tab will contain between 1 and 50 characters, inclusive.
-
Each element of tab will contain the same number of elements.
-
stringsA and tab will contain the same number of elements.
-
Each element of stringsA will be between -50 and 50, inclusive.
-
stringsB will contain between 1 and 50 elements, inclusive.
-
Each element of stringsB will be between -50 and 50, inclusive.
-
d will be between -50 and 50, inclusive.
-
Each element of tab will contain only dashes ('-'), digits ('0'-'9'), and uppercase letters ('A'-'Z').
Examples
0)
 
   
{"-----------------",
 "-------------0-1-",
 "---------0-2-----",
 "---0-2-3---------",
 "-3---------------",
 "-----------------"}
{28,23,19,14,9,4}
{9}
0
Returns: {"-3-5-7-8-A-C-E-F-" }
This sequence of sounds (an octave of a major scale), played on several guitar strings, could be also played on a single string (the 5th one).
1)
 
   
{"-4457754-20024422-4457754-20024200-"}
{0}
{28,23,19,14,9,4}
12
Returns:
{"-----------------------------------",
 "-----------------------------------",
 "----00---------------00------------",
 "-223--32-0--02200-223--32-0--020---",
 "----------33---------------33---33-",
 "-----------------------------------" }
This time, we have a sequence of sounds played on a single string (the beginning of Beethoven's Ode to Joy), and we want to play it on several strings of the guitar. We also make each sound higher by 12 semitones.
2)
 
   
{"-----------------------------------",
 "-----------------------------------",
 "----00---------------00------------",
 "-223--32-0--02200-223--32-0--020---",
 "----------33---------------33---33-",
 "-----------------------------------"}
{28,23,19,14,9,4}
{33,28,24,31}
12
Returns:
{"-----------------------------------",
 "-001--10-----00---001--10-----0----",
 "---------2002--22---------2002-200-",
 "----00---------------00------------" }
We translate the guitar tablature from the previous example to be played on a ukulele. Note that the strings of a ukulele are not ordered from highest to lowest.
3)
 
   
{"-----0------2-2222--0-------0-",
 "----0------2---222---5-----55-",
 "---0------2-----22----9---999-",
 "--0------2-------2-----E-EEEE-",
 "-0------2---------------------",
 "0------2----------------------"}
{28,23,19,14,9,4}
{33,28,28}
12
Returns:
{"xxx-27-xx-049-999x--7777-777x-",
 "xxx----xx-------5x---------Cx-",
 "xxx3---xx0-----99x--------CCx-" }
It is sometimes impossible to play a chord, for example, when one of the sounds is too low for the second instrument, or when it doesn't have enough strings.
4)
 
   
{"012345---------",
 "---------UVWXYZ"}
{-2,2}
{0}
0
Returns: {"xx0123---WXYZxx" }
The first two sounds are too low to be played on this string. The last two sounds are too high.
5)
 
   
{"0220----02--",
 "75--75----57",
 "------B9B9B9",
 "--242424----"}
{33,28,24,31}
{33,28,28}
0
Returns: {"222222222222", "------------", "555555555555" }
One chord played in many different ways on a ukulele. Since we always start assigning the strings from the sound of the highest pitch, our method transforms them all to be played in the same way on a balalaika.
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

Problem Statement
     
The game of Errant Knights is played on an infinite chessboard using two knights, white and black. The players alternate turns and the white player starts the game. Each player makes a normal chess knight's move with his knight, but there is a restriction that each move must make the Euclidean distance between the two knights smaller. A player can make more than one move in a single turn, but then each move must go in the same direction.  For example, if the black knight is at coordinates (0, 0) and the white knight is at (9, 5), then the white knight can move to (7, 4), (5, 3), (3, 2), (1, 1), (-1, 0). Further moving in this direction is not allowed because (-3, -1) is further from (0, 0) than (-1, 0). Of course, the white knight could also start his turn by moving in one of several other directions, and then possibly making more moves in that direction.  The game ends when one of the knights wins by capturing the other one (by moving to its position), or when it is impossible to make another move (because the knights are orthogonally next to each other and each move would increase the distance). In the second case, the player who should make the next move loses.  Several games of Errant Knight will be played. The starting position of the white knight in the i-th game is (x[i], y[i]). The black knight will start each game at (0, 0). Both players play optimally. Return a String where the i-th character is 'B' if the black knight wins the i-th game or 'W' if the white knight wins.
Definition
   
Class:
ErrantKnight
Method:
whoWins
Parameters:
vector <int>, vector <int>
Returns:
string
Method signature:
string whoWins(vector <int> x, vector <int> y)
(be sure your method is public)
   
 
Notes
-
A chess knight can move in 8 directions. From (0, 0), a knight could move to (2, 1), (2, -1), (1, 2), (-1, 2), (1, -2), (-1, -2), (-2, 1), (-2, -1).
Constraints
-
x and y will contain between 1 and 50 elements, inclusive.
-
x and y will contain the same number of elements.
-
Each element of x will be between -4000 and 4000, inclusive.
-
Each element of y will be between -4000 and 4000, inclusive.
-
For each i, x[i] and y[i] cannot both be equal to 0.
Examples
0)
 
   
{1,1,2,2,9,3}
{0,1,0,1,5,3}
Returns: "BWWWWB"
In the first game, there is no possible move for White from (1,0), so Black wins. In the second game, White moves from (1,1) to (0,-1). Black has no legal move from there, so White wins. In the third game, White moves from (2,0) to (0,1). Again, Black has no legal move, and White wins. In the fourth game, White moves from (2,1) to (0,0), and captures the Black knight. White wins. In the fifth game, White makes five moves from the same direction, moving from (9,5) to (-1,0). White wins. In the sixth game, White can make a sequence of moves which lead to one of the following squares: (2,1), (1,-1), (1,2), (-1,1), (4,1), (1,4). After each of these moves Black can win.
1)
 
   
{1,2,3,4,5,6,7,1,2,3,4,5,6,7,1,2,3,4,5,6,7,1,2,3,4,5,6,7,1,2,3,4,5,6,7,1,2,3,4,5,6,7,1,2,3,4,5,6,7,7}
{0,0,0,0,0,0,0,1,1,1,1,1,1,1,2,2,2,2,2,2,2,3,3,3,3,3,3,3,4,4,4,4,4,4,4,5,5,5,5,5,5,5,6,6,6,6,6,6,6,7}
Returns: "BWBBBBBWWWWWWWWWWWWWWWWBWWWWWWWBWWWWWWWBWWWWWWWWWB"
 
2)
 
   
{-10}
{0}
Returns: "B"
Note that x[i] and y[i] can be negative.
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.