Jolly Jumpers..~

Problem Statement
     
A sum rectangle is a rectangle divided into a grid of unit squares. Each square contains a number, and the numbers in neighboring squares always satisfy the following property:
The number in any square S that is neither in the bottom row nor in the right column can be computed as the sum of the following three numbers:
The number in the square directly below S.
The number in the square directly to the right of S.
The number in the other square adjacent to the previous two squares (the one diagonally down and to the right of S).
An example of a correctly filled sum rectangle:
+----+----+----+----+----+
| 88 | 57 | 33 | 10 |  5 |
+----+----+----+----+----+
| 18 | 13 | 11 | 12 | -7 |
+----+----+----+----+----+
|  1 |  4 | -2 |  1 | 18 |
+----+----+----+----+----+
For example, in the top left corner we have 88 = 18 + 57 + 13.
We have a secret sum rectangle. You will be given a vector <int> leftColumn containing the leftmost number in each row of our rectangle, from the top to the bottom. You will also be given an vector <int> topRow containing the topmost number in each column of our rectangle, from the left to the right. Compute and return the number in the bottom right corner. If the input is such that this number cannot be determined uniquely, return 0 instead.
Definition
    
Class:
SumRectangle
Method:
getCorner
Parameters:
vector <int>, vector <int>
Returns:
int
Method signature:
int getCorner(vector <int> leftColumn, vector <int> topRow)
(be sure your method is public)
    
 
Notes
-
You may assume that the return value will always fit into an int (i.e., a 32-bit signed integer data type).
Constraints
-
leftColumn will contain between 1 and 10 elements, inclusive.
-
Each element of leftColumn will be between 0 and 100, inclusive.
-
topRow will contain between 1 and 10 elements, inclusive.
-
Each element of topRow will be between 0 and 100, inclusive.
-
Element 0 of leftColumn will be equal to element 0 of topRow.
Examples
0)
 
    
{88,18,1}
{88,57,33,10,5}
Returns: 18
This is the rectangle from the problem statement. The lower right corner is uniquely determined by the left column and the top row.
1)
 
    
{0,0,0,0}
{0,0,0,0}
Returns: 0
The only correct way to fill this rectangle is to place a zero into each square.
2)
 
    
{6,1}
{6,2}
Returns: 3
This is the smallest non-trivial case:
+----+----+
|  6 |  2 |
+----+----+
|  1 | ?? |
+----+----+
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
     
In this problem your goal is to convert a description of how a guitar chord is played to its name. For the purpose of this problem we will only consider major and minor chords.
Musical notes are given the following 12 names, in ascending order: C, C#, D, D#, E, F, F#, G, G#, A, A#, B.
The difference between two succesive notes is called a half-step. The order of notes is cyclic. That is, the note one half-step higher than B is again C, and the note two half-steps lower than C is A#. Notes that are a multiple of 12 half-steps apart have the same name, and for our purposes we will consider them equivalent.
In this problem we will consider a six-string guitar with standard tuning. The six strings of such a guitar are tuned to the following notes, in order: E, A, D, G, B, E. (Guitar players, please note that the order used starts with the lowest string.)
If you play an open string, you will hear the corresponding note. For example, if you play the A string, you will hear the note A. To change the note the string plays, you can hold it down on one of the frets. If you play a string while holding it down on the K-th fret, you will hear a note that is K half-steps higher. For example, if you play the A string while holding it down on the 4-th fret, you will hear the note C#.
You will be given a guitar chord encoded as a vector <int> chord with six elements, each of them describing one string of the guitar in the order given above. For each string we are given the fret where to hold it down. The value 0 represents an open string that plays the original note, and the special value -1 is used for a string that is not played in the chord.
For example, suppose that chord = {-1, 3, 2, 0, 1, 0}. When playing this chord, you will hear the following notes: {none, C, E, G, C, E}.
The above chord contains three distinct notes: C, E, and G. This chord is called the "C Major" chord.
For any note X, the "X Major" chord is formed by three distinct notes. It can be obtained from the "C Major" chord by shifting all three notes by the same number of steps so that C becomes X. For example, if we shift the notes (C,E,G) by three steps, we get the notes (D#,G,A#). These three notes form the "D# Major" chord.
Similarly, the chord "C Minor" is formed by the notes C, D#, and G, and all other minor chords are shifts of this chord.
Given the vector <int> chord, decide whether it is one of the 12 major or one of the 12 minor chords, as defined above. If it is one of these chords, return its name as a string ("X Major" for major chords, "X Minor" for minor chords). If the chord represented by chord is not one of our chords, return an empty string.
Definition
    
Class:
WhatsThisChord
Method:
classify
Parameters:
vector <int>
Returns:
string
Method signature:
string classify(vector <int> chord)
(be sure your method is public)
    
 
Notes
-
When classifying a chord the only thing that matters is the set of notes played. The number of times a note is played does not matter as long as each of the required notes is played at least once.
Constraints
-
chord will contain exactly 6 elements.
-
Each element of chord will be between -1 and 12, inclusive.
Examples
0)
 
    
{-1, 3, 2, 0, 1, 0}
Returns: "C Major"
This is the C Major chord, as described in the problem statement.
1)
 
    
{3,2,0,0,0,3}
Returns: "G Major"
This is another of the basic guitar chords. The strings play the following notes: G, B, D, G, B, G. If we take the C Major chord (C,E,G) and shift it by 7, we get (G,B,D), which is precisely the set of notes in this chord. Hence the chord is G Major.
2)
 
    
{-1,0,2,2,1,0}
Returns: "A Minor"
This is the most common way of playing the A Minor chord. The three distinct notes we hear in this case are A, C, and E.
3)
 
    
{-1,4,3,1,2,1}
Returns: "C# Major"
 
4)
 
    
{8,10,10,9,8,8}
Returns: "C Major"
There are multiple ways to play each chord.
5)
 
    
{0,0,0,0,0,0}
Returns: ""
This is not one of our 24 simple chords.
6)
 
    
{-1,-1,4,-1,-1,7}
Returns: ""
Neither is this.
7)
 
    
{-1, -1, 2, 0, 1, 0}
Returns: "C Major"
The notes played in this chord are {none, none, E, G, C, E}. The set of notes played is (C,E,G), hence this is again a C Major chord. (In music theory this chord has a more precise name C/E, but this is irrelevant. It is still a C Major chord.)
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
     
You have a machine that cuts glass panes using a robotic arm with a diamond point at the end.
The input to the machine is a rectangular piece of glass with width W and height H. The machine has a coordinate system with point (0,0) in one corner of the glass pane and (W,H) in the opposite corner. In the beginning, the diamond point is positioned at (startx,starty). Then the machine executes a given program.
The program is given as a vector <string> program. Concatenate the elements of program to get one long string that describes the program. Each character in the program describes one movement of the diamond point: 'L' decreases its x-coordinate, 'R' increases its x-coordinate, 'U' decreases its y-coordinate and 'D' increases its y-coordinate by 1. During all movements, the diamond point cuts the glass.
Once the cutting is over, the glass may fall apart into multiple pieces. Compute and return their count.
Definition
    
Class:
CuttingGlass
Method:
pieces
Parameters:
int, int, int, int, vector <string>
Returns:
int
Method signature:
int pieces(int W, int H, int startx, int starty, vector <string> program)
(be sure your method is public)
    
 
Constraints
-
W will be between 1 and 1000, inclusive.
-
H will be between 1 and 1000, inclusive.
-
startx will be between 0 and W, inclusive.
-
starty will be between 0 and H, inclusive.
-
program will contain between 1 and 50 elements, inclusive.
-
Each element of program will contain between 1 and 50 characters, inclusive.
-
Each character in each element of program will be one of 'L', 'R', 'U', and 'D'.
-
The program will be such that the diamond point never leaves the glass pane, but it may touch the boundary and even cut along the boundary.
Examples
0)
 
    
100
100
50
50
{"ULDR"}
Returns: 2
This program cuts out a small square piece from a large plate.
1)
 
    
10
10
3
4
{"UDUDUDUDUDU"}
Returns: 1
After this program is executed, there will be a short cut on the glass pane, but it will still be in one piece.
2)
 
    
3
3
0
0
{"RDDDUUU","RDDDUUU","R","DLLLRRR","DLLL"}
Returns: 9
This program cuts a 3x3 glass pane into nine separate 1x1 squares.
3)
 
    
5
3
5
3
{"LULLULLU"}
Returns: 2
 
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.