IOI '97 - Cape Town, South Africa

The Toxic iShongololo

"iShongololo" is the Zulu name for a millipede. They are long, shiny, black arthropods with many legs.

The iShongololo eats through an edible "fruit" which for the sake of this problem can be considered a rectangular solid with integer dimensions of L (length), W (width) and H (height).

You are required to write a program that maximizes the number of blocks eaten by the iShongololo without violating the constraints given. The program must output the actions that the iShongololo makes as it eats its way through the fruit.

The iShongololo starts outside the fruit. The first block the iShongololo must eat is 1, 1, 1 and it must then move to this block. It stops when no more blocks can be legally eaten and it can no longer move.

Constraints:

1. The iShongololo occupies exactly one empty block.
2. The iShongololo can only eat one complete block at a time.
3. The iShongololo cannot move to a position where it has previously moved to (that is, move backwards or cross its path).
4. The iShongololo cannot move to a solid (uneaten) block, or outside the fruit.
5. The iShongololo may only move to or eat blocks with whom it shares a face. It may only eat blocks which have no other faces exposed to empty eaten blocks.

Input Format

As input your program will receive three numbers (integers) which are the length (L), width (W) and height (H) of the solid.

The three integers L, W, H, are each on a separate line. The three integers will be between 1 and 32 (inclusive).

Output Format

The output consists of lines that begin with 'E' (eat) or 'M' (move) followed by 3 integers that represent the block eaten or moved to on the axes corresponding to L, W, H.

Sample Input

2
3
2

Length of solid is 2.
Width of solid is 3.
Height of solid is 2.

Sample Output

E 1 1 1
M 1 1 1
E 2 1 1
E 1 1 2
E 1 2 1
M 1 2 1
E 1 3 1
M 1 3 1
E 2 3 1
E 1 3 2
M 1 3 2

Eat the block 1 1 1
Move to the block 1 1 1
Eat the block 2 1 1
Eat the block 1 1 2
Eat the block 1 2 1
Move to the block 1 2 1
Eat the block 1 3 1
Move to the block 1 3 1
Eat the block 2 3 1
Eat the block 1 3 2
Move to the block 1 3 2

Scoring

• If the iShongololo violates the constraints, then your solution receives 0 points.
• The total score is the percentage of blocks eaten as a proportion to an excellent solution of the IOI organisers, rounded to the nearest integer percent.
• A solution cannot score more than 100%.

All Submissions
Best Solutions

Point Value: 20 (partial)
Time Limit: 2.00s
Memory Limit: 32M
Added: Dec 26, 2013

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)