행성계 만들기

마스 교수는 행성이 만들어지는 과정을 손으로 시뮬레이션한다. 이 시뮬레이션을 프로그램으로 옮겨 달라는 부탁을 받았다.

시뮬레이션은 작은 미행성이 서로 충돌해 큰 행성이 되는 과정을 다룬다. 공간은 $n_x \times n_y \times n_z$ 크기의 정육면체 격자로 나뉘고, 각 칸에는 미행성이 최대 하나만 들어간다. 미행성마다 질량 $m$, 처음 위치 $(x, y, z)$, 속도 $(v_x, v_y, v_z)$가 주어진다. 속도는 1초 동안 각 축 방향으로 지나가는 칸 수다. 예를 들어 위치가 $(1, 3, 2)$이고 속도가 $(3, -1, 2)$인 미행성은 1초 뒤에 $(4, 2, 4)$, 2초 뒤에 $(7, 1, 6)$에 있다.

경로는 모든 축에서 순환한다. 위 미행성이 $8 \times 8 \times 8$ 공간에 있다면 그다음 두 위치는 $(2, 0, 0)$과 $(5, 7, 2)$다. 칸 번호는 0부터 시작한다.

미행성 둘 이상이 같은 칸에 모이면 하나로 합쳐진다. 합쳐진 미행성의 질량은 모인 질량의 합이다. 속도는 축마다 모인 속도의 합을 모인 개수로 나눈 뒤 0 방향으로 버린 값이다. 질량 12에 속도가 $(5, 3, -2)$인 미행성과 질량 10에 속도가 $(8, -6, 1)$인 미행성이 합쳐지면 질량은 22, 속도는 $(6, -1, 0)$이 된다.

충돌은 정수 시각에만 일어난다고 본다. 더 이상 충돌이 일어날 수 없게 되면 남은 미행성을 행성으로 본다.

첫 줄에 양의 정수 네 개 $n$, $n_x$, $n_y$, $n_z$가 주어진다. $n$은 미행성의 개수로 $n \le 100$이고, $n_x$, $n_y$, $n_z$는 공간의 각 축 크기로 모두 1000 이하다.

다음 $n$개 줄에는 미행성 하나의 정보가 $m\ x\ y\ z\ v_x\ v_y\ v_z$ 형식으로 주어진다. 시각 $t = 0$에서의 질량, 위치, 속도이며 $1 \le m \le 100$, $0 \le x < n_x$, $0 \le y < n_y$, $0 \le z < n_z$, $-1000 \le v_x, v_y, v_z \le 1000$이다. 처음 위치가 같은 미행성은 없다.

첫 줄에 더 이상 충돌이 일어날 수 없을 때 남아 있는 행성의 개수 $p$를 출력한다. 이어서 $p$개 줄에 행성을 하나씩 Pi: m x y z vx vy vz 형식으로 출력한다. Pi는 번호 $i$를 붙인 식별자로 첫 줄은 P0:으로 시작하고 $i$는 $0$부터 $p-1$까지다. 그 뒤는 그 행성의 질량, 위치, 속도다.

위치와 속도는 마지막 충돌이 일어난 시각을 기준으로 한다. 충돌이 한 번도 일어나지 않으면 시각 $t = 0$을 기준으로 한다.

행성은 질량이 큰 것부터 출력한다. 질량이 같으면 위치 $(x, y, z)$의 사전순으로 놓으며 $x$가 작은 것이 앞에 온다.