Connection Status:
Competition Arena > FeudaliasBattle

FeudaliasBattle

SRM 438 · 2009-04-18 · by vexorian

SRM 438 · 2009-04-18 · by vexorian · Brute Force, Simulation
Class Name: FeudaliasBattle
Return Type: double
Method Name: getMinimumTime
Arg Types: (vector<int>, vector<int>, vector<int>, vector<int>, int, int, int)
Problem Statement

Problem Statement

Feudalia's military is preparing a preemptive strike against Banania's military installations. Feudalia has two 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.

Two missile silos may not seem like a lot, but Banania is also a small country with only two military bases. It takes a single missile to destroy a military base. The general has ordered you to destroy both of Banania's military bases in as little time as possible. You are given int[]s siloX, siloY, baseX and baseY. Your silos are located at (siloX[0], siloY[0]) and (siloX[1], siloY[1]), and the enemy bases are located at (baseX[0], baseY[0]) and (baseX[1], baseY[1]). Return the minimum time in minutes required to destroy both enemy bases.

Notes

  • The Euclidean distance between the i-th silo and the j-th base is: SquareRoot( (siloX[i]-baseX[j])^2 + (siloY[i]-baseY[j])^2 ) .
  • 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, baseY, siloX and siloY will each contain exactly 2 elements.
  • 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)
{100, 500}
{100, 100}
{100, 500}
{300, 300}
6
10
1
Returns: 200.1

At time 0, the silo located at (100, 300) should fire a missile at the base located at (100, 100), and the silo located at (500, 300) should fire a missile at the base located at (500, 100). Each silo is 200 units away from its target, and the missiles travel at a speed of 1 unit per minute. Therefore, it will take 200 minutes for the missiles to reach their targets after they take off. Add 6 seconds of take off time for a total of 200.1 minutes.

1)
{100, 100}
{100, 500}
{100, 500}
{300, 300}
6
10
1
Returns: 210.2

This time it is more convenient to use silo 0 to attack both bases. The second missile launch will start 10.1 minutes after the first launch.

2)
{100, 100}
{100, 500}
{100, 500}
{300, 300}
6
20
20
Returns: 22.4606797749979

Although the placement of the bases and silos is the same as in the last case, this time the recharge time and missile speed are high enough to make it more convenient to use both silos and make each silo attack a different base.

3)
{100,100}
{100, 200}
{100,100}
{300, 400}
30
500
10
Returns: 20.5
4)
{100,100}
{100, 200}
{100,100}
{400, 300}
30
500
10
Returns: 20.5
6)
{0,0}
{0,1}
{1000000,1000000}
{999999,1000000}
30
10
1
Returns: 1414213.3552664907

A large result.

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

Coding Area

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

Submitting as anonymous