| | PROBLEM STATEMENT:
A Bird is considered migratory if it can be found in two regions in different
parts of the year. Of course, it must stay in those regions for a minimum
amount of time (one day in Barbados does not make a migration). The bird can
travel inside those regions and that travel is unimportant (The bird can leave
Alaska for Florida and spend some time in both southern and northern Florida
but those COULD just be considered part of spending time in Florida). The bird
can also travel when not in those regions and that travel can be ignored (The
bird can spend the summer in Alaska and the winter in Brazil, and if the bird
is in England in the spring, who cares?). In this problem we will specify that
the time a bird must spend in a region is at least 90 days. The distance
between these regions must be at least 1000 miles for the bird to be considered
migratory.
To put it precisely, the bird is migratory if there exist 2 blocks of time in
the same calendar year that are each at least 90 contiguous days in length in
which all areas the bird is at in time period 1 are at least 1000 miles away
from all areas the bird is at in time period 2.
Write a class Birds which contains a method isMigratory. isMigratory should
determine whether the given set of bird moves describe a migratory bird. If
so, return 1, otherwise return 0.
Example:
If the bird is in New York in January, and in Connecticut from February through
April, and then spends the rest of the year in Brazil, (which is at least 1000
miles from both New York and Connecticut) that Bird would be considered
migratory because it is spending 31 + 28 + 31 + 30 = 120 consecutive days in
the region containing New York and Connecticut and 365 - 120 = 245 consecutive
days in Brazil.
DEFINITION:
Class Name: Birds
Method Name: isMigratory
Parameters: String[]
Returns: int
Method Signature: int isMigratory(String[] birdMoves)
(be sure your method is public)
TopCoder will enforce the following rules:
*birdMoves has between 1 and 15 elements, inclusive.
*each element of birdMoves will contain between 1 and 50 characters, inclusive.
*each String in birdMoves is of the form
"<gridCoordinateX>,<gridCoordinateY>,<month>,<day>" where <gridCoordinateX>,
<gridCoordinateY>, <month>, and <day> all represent integer values. (The
quotes and angle-brackets are for clarity only).
*<gridCoordinateX> and <gridCoordinateY> will each be between 0 and 30000,
inclusive. The pair <gridCoordinateX>, <gridCoordinateY> represents a location
where the bird begins to reside at the point in time represented by the pair
<month>, <day>.
*<month> will be between 1 and 12, inclusive.
*<day> will be appropriate to the month on a non leap year. That is, if
<month> is 2, then <day> will be restricted to being between 1 and 28, inclusive.
*grid coordinates represent one mile for each unit.
*the distance between a grid cordinate (x1, y1) and (x2, y2) is given by the
square root of the value ((x2 - x1)^2 + (y2 - y1)^2).
*two different elements of birdMoves cannot contain the same date.
NOTES:
*Sort birdMoves by date.
*Assume that the bird begins to exist on the earliest day given in the
birdMoves.
*The bird begins that day at the associated grid coordinate.
*Then, the bird moves instantly, at midnight on the date represented by the
next element of birdMoves to the position represented by the next element of
birdMoves.
*The bird will exist at the location given by the last element of birdMoves
until and including the entire day of December 31.
*January(1), March(3), May(5), July(7), August(8), October(10), December(12)
each have 31 days.
*April(4), June(6), September(9), November(11) each have 30 days.
*February(2) has 28 days.
WORKED EXAMPLES:
birdMoves = { "0,0,1,1", "1000,1000,6,1" }
The bird is at grid coordinate (0,0) from January 1 through May 31. Then, the
bird is at grid coordinate (1000,1000) through December 31. The distance
between (0,0) and (1000,1000) is sqrt( (1000 - 0) ^ 2 + (1000 - 0) ^ 2 ) =
sqrt(2000000) >= 1000. The number of days spent at (0,0) is 31 + 28 + 31 + 30
+ 31 = 151 >= 90, and the number of days spent at (1000,1000) is 365 - 151 =
214 >= 90. Return 1.
birdMoves = { "0,0,1,1", "100,100,6,1" }
The bird is at grid coordinate (0,0) from January 1 through May 31. Then, the
bird is at grid coordinate (100,100) through December 31. The distance between
(0,0) and (100,100) is sqrt( (100 - 0) ^ 2 + (100 - 0) ^ 2 ) = sqrt(20000) <
1000. Return 0.
birdMoves = { "1000,0,2,1", "1000,1000,1,1", "10000,30000,7,1" }
The bird is at (1000,1000) for 31 days, then at (1000,0) for 150 days, then at
(10000,30000) for 184 days.
The distance from (1000,0) to (10000,30000) is 31320.919...
Thus, the bird spends 150 consecutive days (at 1000,0) at least 1000 miles away
from where the bird spends 184 consecutive days (at 10000,30000). Return 1.
{ "30000,30000,9,1", "0,0,1,1", "1000,1000,5,1" } returns 1.
In this case, the bird is migratory based on any of three distance checks. The
bird spends 4 months at (0,0), 4 months at (1000,1000), and 4 months at
(30000,30000). Each of these three spots is at least 1000 miles from the
others. The amount of time spent by the bird in each spot is at least 90 days.
Return 1.
TEST CASES:
{ "0,0,1,1", "00708,708,6,1" } returns 1.
{ "200,400,7,1", "100,0,1,1", "200,200,3,1", "0,400,11,1", "407,308,5,1",
"100,600,9,1" } returns 0.
|