MATE  Materializer
Original problem statements can be found here: in Polish and in English.
Chef Christopher just made his dream come true. He opened a company that produces custommade cookie cutters. First customers already placed their orders (not all of the shapes are suitable for cookie cutters, but oh well  customer is always right).
Christopher bought a special machine  Materializer 3000. It can produce any given threedimensional shape, you have to program it beforehand though.
Every order consists of a layers. Every layer is a table of cubes with edge length 1, with b rows and c columns. For every cube customer specifies whether he wants it filled or not. Layers are numbered starting with 1, lowest to highest, row starting with 1 and top to bottom, and columns starting with 1, left to right.
Materializer works as follows: at the start, specialized part of the machine (called extruder) is on the first layer, first row and first column. Extruder can move around, and fill any cube with a special material. First layer is at the very bottom  a shape is produced starting from the bottom towards the top. Extruder can move freely within a layer, but after moving up a layer it can't go lower again.
Materializer accepts the following commands, and executes them in sequence:
 M x y  move the extruder by x columns and y rows. ( x,y from {1,0,1} ),
 N  move the extruder up a layer,
 E  fill the current cube with material,
 C  end.
To produce a stable shape, you have to satisfy some requirements. A cube on layer w, in column x and row y can be filled with material only if at the time of executing "E" command one of the following conditions is true:
 w = 1 (extruder is on the first layer),
 cube in the position (w1, x, y) is already filled,
 there exists a sequence of positions (x,y) = (x_{0},y_{0}) , (x_{1}, y_{1}), ..., (x_{n}, y_{n}) such that:
 1 <= n <= k,
 for i >= 1 it is true that x_{i1}x_{i} + y_{i1}y_{i} = 1,
 for i >= 1, cube in the postition (w, x_{i}, y_{i}) is filled,
 cube in the position (w1, x_{n}, y_{n}) is filled.
It's possible that you can't fulfill a given order without violating those constraints. To deal with this, you can produce additional cubes (acting as a "scaffolding"), and then remove it. Please help Chris  find a sequence of move that will produce given orders quickly, without wasting too much material.
Input
The first line contains a single integer t <= 7, denoting number of testcases. Then, testcases follow.
First line of the testcase consist of four integers c, b, a, k (1 <= c, b, a <= 30, 1 <= k <= 3)  dimensions of the given order and the stability coefficient. Then, layers follow.
Description of a layer consist of b lines. Every line is a string of length c. Character in the line number y and column x corresponds to a cube in xth column and yth row  "#" denotes that cube has to be filled, "_" means that this cube may remain empty.
Output
For every testcase you should output a sequence of moves that fills out all cubes specified in the order. Given sequence can also fill out any cubes that are not specified there (doesn't matter if it's easy to remove them later). Extruder cannot move outside a cuboid containing the order (a*b*c). Sequence of moves has to end with a command "C". Maximum allowed number of moves is 4*a*b*c.
Example
Input:
1 5 3 4 1 _____ #___# _____ _____ ##### _____ _____ __#__ _____ _###_ _###_ _###_
Output:
M 0 1 E M 1 0 M 1 0 E M 1 0 M 1 0 E N E M 1 0 E M 1 0 E M 1 0 E M 1 0 E N M 1 0 E M 1 0 E M 1 0 E N E M 1 0 E M 1 0 E M 0 1 E M 1 0 E M 1 0 E M 0 1 M 0 1 E M 1 0 E M 1 0 E C
Sample visualization
Scoring
If there are r commands given, and there are n additional cubes, then a score for the given order is (r+10n)/(a*b*c). The less points, the better. Final testcase score is a sum of scores for all of the orders. In the sample testcase r=45, n=3 so the score is 75/(4*3*5) = 1.25.
hide comments
Mitch Schwartz:
20210201 22:00:28
Thank you! And, it's a very nice problem. 

Piotr Jagie³³o:
20210201 19:05:32
Thanks for reporting this, the judge was in fact broken. It's updated now, let me know in case of more problems. 

Mitch Schwartz:
20210130 11:16:31
@Piotr Jagiełło I have some doubts about the judge, as I added code to verify my output with asserts, but none of the asserts were tripped and I still got WA. (Submission 27362297 was just a test with assert(0) to make sure the judge doesn't suppress runtime errors.)

Added by:  Piotr Jagiełło 
Date:  20180330 
Time limit:  10s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  PIZZA 2018 qualifying round 