50045. Mines and Black Holes

I'm a slow walker, but I never walk backwards.

Task Description

Read problem statements in 中文

A spaceship is traveling in a 3D space. Given the initial position of the spaceship and a series of $N$ instructions, simulate the movements of the spaceship and output its positions periodically.

The initial position of spaceship is $(x_0, y_0, z_0)$. It will move according to instructions. Each instruction is a number from $1$ to $6$, indicating the direction the spaceship should go. Let the current position of spaceship be $(x, y, z)$:

  • $1$ - The spaceship moves from $(x, y, z)$ to $(x+1, y, z)$
  • $2$ - The spaceship moves from $(x, y, z)$ to $(x-1, y, z)$
  • $3$ - The spaceship moves from $(x, y, z)$ to $(x, y+1, z)$
  • $4$ - The spaceship moves from $(x, y, z)$ to $(x, y-1, z)$
  • $5$ - The spaceship moves from $(x, y, z)$ to $(x, y, z+1)$
  • $6$ - The spaceship moves from $(x, y, z)$ to $(x, y, z-1)$

There are a mine and a black hole in the space. The mine is located at $(x_m, y_m, z_m)$ and the black hole is located at $(x_b, y_b, z_b)$.

The distance between two points in space is the sum of the absolute values of the differences between their coordinates in all three dimensions. That is, the distance between two points $p = (x_p, y_p, z_p)$ and $q = (x_q, y_q, z_q)$ is defined as
$$\text{dist}(p, q) = \vert x_p-x_q\vert + \vert y_p-y_q\vert + \vert z_p-z_q\vert ;\text{.}$$

Both mine and block hole will attract the spaceship within a certain range. When the distance between the spaceship and the mine is smaller than $10$ units, the spaceship will be attracted to the mine and explode at location $(x_m, y_m, z_m)$. The spaceship cannot travel after the explosion, so you can ignore any further instructions. When the distance between the spaceship and the black hole is smaller than $10$ units, the spaceship will be attracted to the black hole, the black hole will then disappear and the spaceship will continue traveling from $(x_b, y_b, z_b)$.

The attraction of the mine is greater than the attraction of the black hole. Therefore, after a movement, if the distances between the spaceship to both the mine and the black hole are smaller than $10$ units, the spaceship will be attracted to the mine and explode.

Given the initial position of the spaceship $(x_0, y_0, z_0)$, the position of the mine $(x_m, y_m, z_m)$, the position of the black hole $(x_b, y_b, z_b)$ and a series of $N$ movement instructions $m_1, m_2, \cdots, m_N$, output the position of the spaceship every $5$ instructions, i.e., output the position after $m_5, m_{10}, m_{15}, \cdots, m_{\lfloor{\frac{N}{5}}\rfloor\times 5} $. Note that if the spaceship explodes after $m_k$, you do not need to output anything after the explosion even if $k$ is a multiple of $5$.

For the given three points $(x_0, y_0, z_0)$, $(x_m, y_m, z_m)$ and $(x_b, y_b, z_b)$, the distance between any two of them will not be smaller than $10$ units.

Input Format

There are four lines in the input file. The first line contains three integers $x_0, y_0, z_0$, representing the initial position of the spaceship. The second line contains six integers $x_m, y_m, z_m, x_b, y_b, z_b$, representing the positions of the mine and the black hole. The third line contains a single integer $N$, representing the number of movement instructions. Finally, the last line contains $N$ integers $m_1, m_2, \cdots, m_N$, representing the $N$ movement instructions.

Technical limitation

  • $\text{dist}((x_0, y_0, z_0), (x_m, y_m, z_m)) \geq 10$, $\text{dist}((x_0, y_0, z_0), (x_b, y_b, z_b)) \geq 10$, $\text{dist}((x_m, y_m, z_m), (x_b, y_b, z_b)) \geq 10$
  • $5 \leq N \leq 50$
  • $1 \leq m_1, m_2, \cdots, m_N \leq 6$
  • $-50 \leq x_0, y_0, z_0, x_m, y_m, z_m, x_b, y_b, z_b \leq 50$

Output Format

If the spaceship doesn't explode, output $\lfloor{\frac{N} {5}}\rfloor$ lines. The $i$-th line contains three integers $x_i, y_i, z_i$, representing the position of the spaceship after $m_{i\times 5}$.

If the spaceship explodes after simulating $m_k$, output $\lfloor{\frac{k-1}{5}}\rfloor$ lines. The $i$-th line contains three integers $x_i, y_i, z_i$, representing the position of the spaceship after $m_{i\times 5}$.

Sample Input 1

-7 1 7
-3 -5 3 0 8 -1
5
6 2 4 4 3

Sample Output 1

-8 0 6

Sample Input 2

3 0 -3
2 4 4 -5 3 -2
25
2 4 1 5 3 5 6 1 3 2 1 1 2 6 5 5 1 3 3 3 4 3 3 3 6

Sample Output 2

3 0 -2
3 1 -2
4 1 -2

Discussion