|
|
3599 - Go Go Gorelians |
||||
|
|
|||||
El recorrido de Gorelians a través del espacio usa acoplamientos de deformación. El recorrido con un acoplamiento de la deformación es instantáneo, pero por razones de seguridad, un individuo puede combar solamente una vez cada 10 horas.
También, el costo de crear un acoplamiento de la deformación aumenta directamente con la distancia lineal entre los puntos finales del acoplamiento.
Los Gorelians, siendo la fuerza dominante en el universo conocido, a menudo se aburren, entonces ellos con frecuencia conquistan nuevas regiones del espacio en la manera siguiente.
- La fuerza inicial de la invasión encuentra un planeta conveniente y lo conquista, estableciendo un gobierno galáctico regional de Gorelians, de aquí en adelante se refirió como el RGGG, que gobernará todas las materias de Gorelians en esta región del espacio.
- Cuando se conquista el planeta siguiente, un solo acoplamiento de la deformación se construye entre el planeta nuevo y el planeta de RGGG. Los planetas conectados vía acoplamientos de la deformación de este modo serían la parte de la red planetaria regional de Gorelians, es decir, el RGPN.
- Mientras que se conquistan los planetas adicionales, cada planeta nuevo está conectado con un solo acoplamiento de la deformación con el planeta más cercano ya del RGPN, así guardando el costo de conectar los planetas nuevos con la red a un mínimo. Si dos o más planetas son equidistantes del planeta nuevo, el planeta nuevo está conectado con cualquiera de ellos que fue conquistada primero.
Así pues, una vez cada año de Gorelians, el RGGG analiza el RGPN y se vuelve a poner a una localización óptima. La localización óptima se define como planeta que reduzca al mínimo el número máximo de las deformaciones requeridas para alcanzar el RGGG de cualquier planeta en el RGPN. Pues resulta, que hay siempre exactamente uno o dos
Planetas. Cuando hay dos, son siempre directamente adyacentes vía un acoplamiento de la deformación, y el RGGG se divide uniformemente entre los dos planetas.
Su trabajo es escribir un programa que encuentre los planetas óptimos para el RGGG. Para los propósitos de este problema, la región del espacio conquistada por el Gorelians se define como cubo de el cual se extienda (0.0.0) a (1000.1000.1000).
Entrada
La entrada consiste en un sistema de los panoramas donde el Gorelians conquista una región del espacio. Cada panorama es independiente. La primera línea del panorama es un número entero N que especifica el número total de los planetas conquistados por el Gorelians. Las siguientes líneas de N de la entrada especifican, la orden conquistada, las identificaciones y las coordenadas de los planetas conquistados que se agregarán al RGPN, en el formato identificación X Y Z. Una identificación es un número entero a partir de 1 a 1000. X, Y, y Z son números enteros a partir de 0 a 1000. Un solo espacio separa los números. Un valor de N = 0 marca el extremo de la entrada.
Salida
Entrada de la Muestra
5
1 0 0 0
2 0 0 1
3 0 0 2
4 0 0 3
5 0 0 4
5
1 0 0 0
2 1 1 0
3 3 2 0
4 2 1 0
5 3 0 0
10
21 71 76 4
97 32 5 69
70 33 19 35
3 79 81 8
31 91 17 67
52 31 48 75
48 90 14 4
41 73 2 21
83 74 41 69
26 32 30 24
0
Salida de la Muestra
3
2 4
31 97