FeudaliasWar

SRM 438 · 2009-04-18 · by ivan_metelsky

SRM 438 · 2009-04-18 · by ivan_metelsky · Graph Theory, Search

Show categories

Class Name: FeudaliasWar

Return Type: double

Method Name: getMinimumTime

Arg Types: (vector<int>, vector<int>, vector<int>, vector<int>, int, int, int)

Problem Statement

Feudalia's military is preparing a preemptive strike against Banania's military installations. Feudalia has a number of missile silos. Each silo has an unlimited number of missiles at its disposal, but can only fire a single missile at a time. When a missile is fired, it requires takeOffTime seconds before it can take off from its silo. Once it takes off, it requires distance/missileSpeed minutes to reach its target, where distance is the Euclidean distance between the silo and the target. When the missile reaches its target, the target is instantly destroyed. After a missile takes off, its silo requires rechargeTime minutes of preparation before it can launch another missile.

The general has ordered you to destroy all of Banania's military bases in as little time as possible. You are given int[]s siloX, siloY, baseX and baseY which determine the locations of the missile silos and bases. Feudalia's i-th missile silo is located at (siloX[i], siloY[i]) and Banania's j-th base is located at (baseX[j], baseY[j]). Return the minimum time in minutes required to destroy all enemy bases.

Notes

The returned value must be accurate to within a relative or absolute value of 1E-9.

Constraints

takeOffTime will be between 1 and 60, inclusive.
rechargeTime will be between 5 and 1000, inclusive.
missileSpeed will be between 1 and 2000, inclusive.
baseX will contain between 1 and 50 elements, inclusive.
baseY will contain the same number of elements as baseX.
siloX will contain between 1 and 50 elements, inclusive.
siloY will contain the same number of elements as siloX.
Each element of baseX, baseY, siloX and siloY will be between 0 and 1000000, inclusive.
The locations for each base and silo will be distinct.

Examples

{1,20002,40003,60004,80005,100006,120007,140008,160009,180010,200011,220012,240013,260014,280015,300016,320017,340018,360019,380020,400021,420022,440023,460024,480025,500026,520027,540028,560029,580030,600031,620032,640033,660034,680035,700036,720037,740038,760039,780040,800041,820042,840043,860044,880045,900046,920047,940048,960049,980050}
{1,20002,40003,60004,80005,100006,120007,140008,160009,180010,200011,220012,240013,260014,280015,300016,320017,340018,360019,380020,400021,420022,440023,460024,480025,500026,520027,540028,560029,580030,600031,620032,640033,660034,680035,700036,720037,740038,760039,780040,800041,820042,840043,860044,880045,900046,920047,940048,960049,980050}
{1,20002,40003,60004,80005,100006,120007,140008,160009,180010,200011,220012,240013,260014,280015,300016,320017,340018,360019,380020,400021,420022,440023,460024,480025,500026,520027,540028,560029,580030,600031,620032,640033,660034,680035,700036,720037,740038,760039,780040,800041,820042,840043,860044,880045,900046,920047,940048,960049,980050}
{980050,960049,940048,920047,900046,880045,860044,840043,820042,800041,780040,760039,740038,720037,700036,680035,660034,640033,620032,600031,580030,560029,540028,520027,500026,480025,460024,440023,420022,400021,380020,360019,340018,320017,300016,280015,260014,240013,220012,200011,180010,160009,140008,120007,100006,80005,60004,40003,20002,1}
60
1000
1
Returns: 693144.5934934405

{0,0,50}
{0,50,0}
{50,0,1000}
{50,1000,0}
30
20
1
Returns: 91.5

An optimal strategy would be: 00:00 : The silo at (50,50) launches an attack against the base at (0,0). 00:30 : The first missile finishes taking off. 20:30 : The silo at (50,50) launches its second missile, this time against the base at (0,50). 21:00 : The second missile finishes taking off. 41:30 : The silo at (50,50) launches its third missile, this time against the base at (50,0). 71:00 : The second missile hits the base at (0,50) (The distance was 50). 71:12.6 (Approx.) : The first missile hits the base at (0,0) (The distance was 70.710678119). 91:30 : The third missile hits the remaining base.

{0,0,50}
{0,50,0}
{50,0,1000}
{50,1000,0}
30
900
1
Returns: 950.5

Since it now takes 15 hours to prepare a new missile, using the same silo against the three enemy bases is no longer the optimal strategy. Instead, each of the silos at (0,1000) and (1000,0) should target the closest base while the silo at (50,50) targets the base at (0,0).

{1000}
{1000}
{0,10,20,30,40,50}
{0,10,20,30,40,50}
45
30
100
Returns: 14.185028842544403

{0,2000,4000,6000,8000}
{0,2000,4000,6000,8000}
{0,2000,4000,6000}
{2000,4000,6000,8000}
60
1000
50
Returns: 1042.0

21)

{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50}
{2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2}
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50}
1
5
2000
Returns: 0.017166666666666667

Minimum result possible (with a big n)

22)

{1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10}
{1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5}
{10000}
{10000}
60
1000
1
Returns: 63181.52946428659

Close to Maximum result possible

85)

{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49}
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}
{999951,999952,999953,999954,999955,999956,999957,999958,999959,999960,999961,999962,999963,999964,999965,999966,999967,999968,999969,999970,999971,999972,999973,999974,999975,999976,999977,999978,999979,999980,999981,999982,999983,999984,999985,999986,999987,999988,999989,999990,999991,999992,999993,999994,999995,999996,999997,999998,999999,1000000}
{1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000}
60
1000
1
Returns: 1414179.9145652682

(by ged) testing precision

Submissions are judged against all 102 archived test cases, of which 8 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class FeudaliasWar with a public method double getMinimumTime(vector<int> baseX, vector<int> baseY, vector<int> siloX, vector<int> siloY, int takeOffTime, int rechargeTime, int missileSpeed) · 102 test cases · 2 s / 256 MB per case