Jolly Jumpers..~

Problem Statement
     
A string S is an interspersal of a set of strings W, if W is a set of disjoint subsequences of S which cover S. Less formally, S can be formed from W by partitioning each member of W into substrings, then concatenating all the substrings, while maintaining the order of the substrings within each element of W. For example, if W contains the strings {"DESIGN", "ALGORITHM", "MARATHON"}, then one possible interspersal would be "ADELGMAORARISIGNTHMTHON", formed as shown below.
  DE         SIGN A  LG  O  RI    THM      MA RA         THON ----------------------- ADELGMAORARISIGNTHMTHON
Given a vector <string> W, return the lexicographically minimum interspersal of the strings in W
Definition
   
Class:
StringInterspersal
Method:
minimum
Parameters:
vector <string>
Returns:
string
Method signature:
string minimum(vector <string> W)
(be sure your method is public)
   
 
Notes
-
The lexicographically minimum of two strings is the one with the alphabetically earlier character at the first position at which they differ.
-
The return string will contain no more than 1000 characters.
Constraints
-
W will contain between 1 and 20 elements, inclusive.
-
Each element of W will contain between 1 and 50 uppercase letters ('A'-'Z'), inclusive.
Examples
0)
 
   
{"DESIGN","ALGORITHM","MARATHON"}
Returns: "ADELGMAORARISIGNTHMTHON"
The example from the problem statement.
1)
 
   
{"TOMEK","PETR","ACRUSH","BURUNDUK","KRIJGERTJE"}
Returns: "ABCKPERIJGERRTJETOMEKTRURUNDUKUSH"
 
2)
 
   
{"CCCA","CCCB","CCCD","CCCE"}
Returns: "CCCACCCBCCCCCCDE"
 
3)
 
   
{"BKSDSOPTDD","DDODEVNKL","XX","PODEEE","LQQWRT"}
Returns: "BDDKLODEPODEEEQQSDSOPTDDVNKLWRTXX"
 
4)
 
   
{"TOPCODER","BETFAIR","NSA","BT","LILLY"}
Returns: "BBELILLNSATFAIRTOPCODERTY"
 
5)
 
   
{"QITHSQARQV","BYLHVGMLRY","LKMAQTJEAM","AQYICVNIKK","HKGZZFFEWC"}
Returns: "ABHKGLKMAQIQQTHSQARQTJEAMVYICVNIKKYLHVGMLRYZZFFEWC"
 
6)
 
   
{"XHCYBTUQUW","EKBISADSSN","LOOISPOFAK","MIXBDHPJUQ","BNMNDHMOTC"}
Returns: "BEKBILMINMNDHMOOIOSADSPOFAKSSNTCXBDHPJUQXHCYBTUQUW"
 
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
     
A particular star system consists of a single star, with N planets orbiting it. Each planetary orbit is a perfect circle of distinct radius centered on the star and all orbits lie in the same 2-D plane. The planets move along their circular paths with constant speed and planet i completes 1 full orbit in the time given by the absolute value of periods[i]. periods[i] will be positive if planet i orbits clockwise and negative if it orbits counter-clockwise. A k-planetary alignment occurs when an infinite straight line exists, passing through the center of the star and through the centers of at least k of the planets. A N-planetary alignment occurs at time T = 0, i.e., all the planets lie in a line at this time (see notes for clarification). Return the number of distinct times between T1 and T2, inclusive, when a k-planetary alignment occurs.
Definition
   
Class:
KPlanetaryAlignment
Method:
number
Parameters:
vector <int>, int, int, int
Returns:
int
Method signature:
int number(vector <int> periods, int k, int T1, int T2)
(be sure your method is public)
   
 
Notes
-
The constraints ensure the return value will fit in a signed 32-bit integer.
-
Alignments can occur with the planets either on the same side of the star or diametrically opposite each other.
-
The configuration of the planets at T = 0 (i.e., whether the planets are all on the same side, or some are diametrically opposite) makes no difference to the answer.
Constraints
-
periods will contain between 2 and 5 elements, inclusive.
-
Each element of periods will be a non-zero integer between -100 and 100, inclusive.
-
The elements of periods will be distinct.
-
k will be between 2 and the number of elements in periods, inclusive.
-
T2 will be between 0 and 50,000,000 (5 * 10^7), inclusive.
-
T1 will be between 0 and T2, inclusive.
Examples
0)
 
   
{8,40}
2
0
20
Returns: 5
Here, the first planet is rotating 5 times as quickly as the second. Ater 5 seconds, the first will have completed 5/8 of an orbit, while the second will have completed 5/40 = 1/8 of an orbit. They are therefore diametrically opposite and this is the first 2-alignment after time 0. Further 2-alignments happen at T = 10, 15 and 20.
1)
 
   
{8,24,40}
2
0
20
Returns: 8
With an additional planet, 2-alignments happen at T = 0, 5, 6, 10, 12, 15, 18, 20.
2)
 
   
{8,24,40}
3
0
100
Returns: 4
3-alignments of the same set of planets happen at T = 0, 30, 60, 90.
3)
 
   
{-10,10}
2
2
26
Returns: 10
Now that the planets are rotating in opposite directions, 2-alignments occur every 2 1/2 seconds.
4)
 
   
{-1,2,3,4,5}
3
10000
50000
Returns: 53333
 
5)
 
   
{-1,1}
2
0
50000
Returns: 200001
 
6)
 
   
{-2,91,87,77,71}
4
0
50000000
Returns: 1471
 
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.