Legendary Archer Octavius
Statement
Goal
The Roman Empire is being attacked by UFOs! It is up to the unassuming city guardsman Octavius, son of Septimus, to defend his city with his trusty bow!Octavius begins on top of a watchtower at coordinates
Octavius must shoot down the N UFOs currently menacing the city. Luckily, they are busy abducting hapless civilians and are thus motionless in the sky. The Bow of Sagittarius is extremely powerful, able to take down a UFO in a single shot. To save as many people as possible, Octavius must find the optimal sequence of actions to take in order to strike down all UFOs in the least amount of time. Report the elapsed time to two decimal places, ending when the final UFO is struck.
For this puzzle, the acceleration due to gravity is
Input
Line 1: An integer N, representing the number of UFOs to shoot
Next N lines: Space separated integers x, y, and z, representing the coordinates of a UFO
Next N lines: Space separated integers x, y, and z, representing the coordinates of a UFO
Output
The shortest possible time in seconds required to strike down all UFOs, reported to two decimal places
Constraints
1 ≤ N ≤ 30
-500 ≤ x,z coordinates ≤ 500
1 ≤ y coordinates ≤ 500
All UFOs are possible to hit
-500 ≤ x,z coordinates ≤ 500
1 ≤ y coordinates ≤ 500
All UFOs are possible to hit
Example
Input
2 200 60 0 30 120 0
Output
6.89
Tags
Ballistics, Scheduling
Difficulty
Hard
Test cases
Trivial Test
Input
2
200 60 0
30 120 0
Output
6.89
Validator Trivial Validator
Input
2
100 164 0
39 111 -180
Output
8.55
Zipline Action Test
Input
3
290 130 160
90 50 20
-60 25 -25
Output
31.04
Validator Zipline Validator
Input
3
100 120 0
15 45 -60
360 95 -100
Output
31.87
Chug, chug, chug! Test
Input
4
200 250 0
100 60 40
-90 40 70
-120 1 1
Output
37.72
Validator Chug Validator
Input
4
230 200 30
160 30 -20
-140 70 -15
0 275 0
Output
36.77
Haste makes waste Test
Input
3
190 200 -10
465 60 -220
-340 20 -105
Output
37.70
Validator Haste Validator
Input
3
-220 5 -370
220 200 0
230 210 -25
Output
37.71
Noclipping UFOs Test
Input
6
200 20 0
300 144 0
301 144 0
-190 180 70
-190 181 70
0 139 0
Output
38.48
Validator Noclip Validator
Input
6
0 5 70
333 98 -111
333 99 -111
200 20 0
180 210 0
181 210 1
Output
38.63
Reinforcements Test
Input
14
152 180 82
193 156 189
-106 166 -17
-124 20 -152
321 25 -103
-272 53 265
21 214 54
112 169 104
117 23 -150
251 116 87
63 1 -46
-140 156 24
122 51 -125
-102 7 75
Output
43.69
Validator Reinforce Validator
Input
14
149 58 214
83 191 58
-148 23 -192
-188 53 69
221 194 19
51 88 -153
310 12 -57
187 134 -129
-216 186 77
-210 104 35
150 49 62
200 200 0
0 49 -200
0 9 380
Output
44.71
Surrounded Test
Input
17
-186 192 -169
-272 102 -270
193 217 -180
114 240 150
55 263 -151
-30 257 214
369 124 -196
206 173 -201
-199 159 -199
75 183 259
117 198 -265
-7 235 -154
-134 239 41
0 47 434
-163 208 153
176 241 168
431 10 419
Output
65.74
Validator Surrounded Validator
Input
17
393 77 304
81 301 78
-118 43 -392
188 253 79
369 244 119
96 218 -222
499 88 -183
302 162 -254
217 184 -329
0 300 0
-291 146 47
210 204 340
150 299 40
200 300 0
0 95 -400
0 95 400
200 196 -194
Output
66.00
Martian Invasion Test
Input
29
152 180 82
193 156 189
-106 166 -17
-124 20 -152
321 25 -103
-272 53 265
21 214 54
-303 30 3
-116 82 -132
-17 105 -281
216 190 83
112 169 104
117 23 -150
251 116 87
63 1 -46
-140 156 24
122 51 -125
-102 7 75
391 22 57
-183 44 67
-3 177 4
2 205 1
28 41 -23
19 191 -124
167 70 -298
218 19 -47
99 99 99
123 43 -21
67 18 192
Output
86.63
Validator Invasion Validator
Input
29
-93 9 -31
17 107 170
90 60 261
-13 83 189
276 35 75
111 111 111
96 81 88
56 131 -38
252 43 -96
289 65 -55
232 10 -116
-94 9 206
15 92 46
10 3 22
246 135 46
291 88 -4
-105 2 -20
86 18 -240
33 19 213
34 105 -66
-19 72 -46
182 55 -205
192 48 22
226 130 0
99 88 77
160 34 -22
-1 59 -3
46 163 2
0 33 -82
Output
86.47
Solution language
Solution
Stub generator input