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. |
| |
Definition |
| | | Class: | FeudaliasWar | | Method: | getMinimumTime | | Parameters: | int[], int[], int[], int[], int, int, int | | Returns: | double | | Method signature: | double getMinimumTime(int[] baseX, int[] baseY, int[] siloX, int[] siloY, int takeOffTime, int rechargeTime, int missileSpeed) | | (be sure your method is public) |
|
| |
|
| |
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 |
| 0) | |
| | {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. |
|
|
| 1) | |
| | {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). |
|
|
| 2) | |
| | {0,2000,4000,6000,8000} | {0,2000,4000,6000,8000} | {0,2000,4000,6000} | {2000,4000,6000,8000} | 60 | 1000 | 50 |
| Returns: 1042.0 | |
|
| 3) | |
| | {1100,1200,1300,1400,1500,1600,1700,1800,1900} | {2100,2300,2500,2700,2900,2700,2500,2300,2100} | {1400,1400,1500,1600,1600} | {3100,3300,3200,3100,3300} | 20 | 300 | 100 |
| Returns: 306.7494291969649 | |
|