CCO '10 P5 - Space Miner

View as PDF

Submit solution

Points: 15
Time limit: 1.0s
Memory limit: 256M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
Canadian Computing Competition: 2010 Stage 2, Day 2, Problem 2

There are M (1 \le M \le 1\,000) planets each with v_i (1 \le v_i \le 10\,000) units of resources and radius r_i (1 \le r_i \le 100).

Starting from (0, 0, 0), you travel in straight lines through N (1 \le N \le 1\,000) waypoints in a specific order.

Whenever you travel within D + r_i (1 \le D \le 50) units from a planet's centre, you can mine the planet using your tractor beam retrieving v_i units of resources. Note that if you are exactly D units from the surface of the planet, you can mine the planet. If your path takes you through a planet, do not worry, since your spaceship can drill through planets, which makes mining even easier. Also note that you cannot mine the same planet on a subsequent visit.

Give the number of minerals that can be mined on your journey.

Hint: you should do all calculations with 64-bit integers.

Input Specification

On the first line of input is the number M, the number of planets. On the next M lines are five integers describing each of the M planets. These integers are x_i\ y_i\ z_i\ v_i\ r_i, where the planet i is at position (x_i, y_i, z_i), (where -1\,000 \le x_i, y_i, z_i \le 1\,000) and this planet has v_i resources and radius r_i. On the next line is the number N, the number of waypoints to pass through. Each of the next N lines contains the position of these waypoints, as three integers x_i\ y_i\ z_i (-1\,000 \le x_i, y_i, z_i \le 1\,000). The last line of input is the number D, the maximum distance from a planet's surface that your ship can be and still mine a planet.

Output Specification

On one line, output the amount of minerals that you can mine on your journey.

Sample Input

10 0 0 1 1
0 10 0 2 1
0 0 10 4 1
8 0 0
0 7 0
0 0 9

Sample Output



There are no comments at the moment.