470. The Death Cube
Time limit per test: 0.25
Memory limit: 262144
input: standardA long time ago, in a Galaxy Far Far Again...
New dangerous mission undertake Jedi Knights. Latest and most powerful weapon of the Empire — the Death Cube — decided they to destroy. Not easy the mission is — new modified battle droids withstand them to, and very complex and awkward structure the Death Cube has. Specifically, many tiers consists the Cube of, and cellular structure each tier has. It is unimportant which face of the cube start you to mark out tiers from — every time distinguish tiers will you be able to. X
tiers in one dimension of the Cube could count you, Y
tiers in the second dimension, and Z
tiers in the third one. Thus, not cube the Death Cube is, but rectangular parallelepiped instead, and XYZ
cabins has the Cube. In other words, in a 3-D space can be allocated the Cube so that in integer point the center of every cabin is, and every integer point inside the Cube is the center of a cabin. In this system between any two cabins passageway exists if and only if exactly one unit the distance between the cabins is. For you convenience, to you example of the Cube with X
=Y=Z=2 is given.
The Cube to destroy, plan to place a bomb in every passageway of the Cube Jedi Knights. So to do, should in some cabin close to the outer surface of the Cube start the mission detachment of Jedis to. From cabin to cabin by moving, should mine they passageways passed, and in one of the cabins close to the outer surface of the Cube should finish their mission Jedi Knights. During their trip cannot separate from each other Jedis — only all together can overpower battle droids they. That what your job is — find the shortest way which should overpass Jedis to.
Several descriptions of Death Cubes input file may contain (since indefatigable the Emperor is, and construct new Cubes continues he to). Only three numbers — X
— contains every line of input (
For every Cube, only length of the shortest way should output you, and the way itself will help to Jedis the Power find to. Output details in example will find you.
2 1 2
2 2 2
Case #1: 4
Case #2: 15
The following way one of the possible solutions to the Cube from the second example (and from the picture) is: 1—2—3—4—1—5—6—2—3—7—6—5—8—4—8—7.