Problem Statement

A musician has composed several melody fragments and wants you to make a program to create a complete melody by appending those fragments. A fragment is described as a sequence of key jumps on a piano keyboard. A piano keyboard looks like this:

For instance, to go from the leftmost C key to the F key, a jump of 5 keys is needed (note that the black keys are counted), and to go back requires a jump of -5 keys. A fragment does not specify a starting position. It could be "2 3 -1" meaning that after the initial key we should move two keys to the right, then three and finally one to the left.

But there is a problem: the musician has set the restriction that the resulting melody must not use (including the starting position) black keys. Then, the fragment shown above could be used either starting on a G key (and then A, C and B) or starting on a C key (and then D, F and E). Each fragment can be used only once in the melody and cannot be used partially.

You are given a String[] fragments, the melody fragments, and you must return the number of fragments in the longest melody that can be created by appending those fragments.

Definition

 Class: CMajor Method: getLongest Parameters: String[] Returns: int Method signature: int getLongest(String[] fragments) (be sure your method is public)

Notes

-Assume that the piano keyboard is infinite.

Constraints

-fragments will contain between 1 and 19 elements, inclusive.
-Each element of fragments will contain between 1 and 50 characters, inclusive.
-Each element of fragments will be a list of integers, each separated by a single space, with no additional leading or trailing spaces.
-Each integer in fragments will be between -10000 and 10000, inclusive, with no leading zeros.

Examples

0)

 `{"2 2 1 2 2 2 1","2 1 2 2 2 1 2"}`
`Returns: 1`
 The first fragment can only be played starting from C and ending on the next C, and the second fragment can only be played starting from D and ending on the next D. Therefore, they cannot be appended.
1)

 `{"2","2","1","2","2","2","1","2","2","1","2","2","2","1","2","2","1","2","2"}`
`Returns: 19`
 All these fragments can be played in order starting from a C key.
2)

 `{"2 2 2 2","1 1","5 -4 12 -11","0 2 -2 5 -1 -4 2 -2 7 -2"}`
`Returns: 1`
 The only fragment that can be played, without using black keys, is the last one.
3)

 `{"2 0 2 0 -2 -2 -1 5 1 2 2 2 1"}`
`Returns: 1`
4)

 ```{"5748 -4385 -790 5294 3349","-3279 -1783 3768 -2459 6066 2556 -8138 -4982 1435", "2951","-2405 2104 3756","5578 -5040 -9497 -4868 7407 9305 -6701", "-3339 9514 -787 7209 7467 -4467", "7496 3011 9941 -8340 3012"}```
`Returns: 4`
5)

 ```{"72","1872","8916","-288","2208","-4716","2328","9516", "-5472","9840","6420","3492","-1608","4176","264","-6264", "1176","-684","3984"}```
`Returns: 19`

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=5903

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9810&pm=5903

esteban

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Dynamic Programming, Search