7714. Milling machines

 

A fab lab is an open, small-scale workshop where you can create or fabricate almost anything you want mostly by using computer controlled tools like a laser cutter or a 3D printer. The FAU fab lab recently got a CNC milling machine. Using the milling machine you can cut or remove material with different tools from the surface of a workpiece. It is controlled via a computer program.

I sometimes wondered what happens if multiple different shaped workpieces are sent through the same milling program. For simplification assume that we have only two dimensional workpieces without holes. A milling program consists of multiple steps; each step describes where the milling machine has to remove material (using different tools) from the top of the surface.

 

Input. The first line consists of two integers w and s (1 ≤ w, s ≤ 104), where w gives the number of workpieces and s the number of steps in the milling program. The next line consists of two integers x and y (1 ≤ x, y ≤ 100), where x gives the width and y gives the maximal possible height of workpieces.

Then follow w lines, each describing one workpiece. Each workpiece description consists of x non-negative integers specifying the surface height in that column.

Then follow s lines, each describing one milling step of the milling program. Each milling step description consists of x non-negative integers si (0 ≤ si ≤ y) specifying the amount of surface to cut off in each column (relative to the height of the milling area, i.e. y, not relative to the top of the workpiece). See Figure for details.

 

Output. For each workpiece, output one line containing x integers specifying the remaining surface heights (in the same order as in the input).

 

Figure. Second workpiece in first sample: initial workpiece followed by milling in each column – the value in the milling program determines the vertical position of the cutter head.

prb7714.gif

 

Sample input 1

Sample output 1

2 1

3 4

4 4 4

4 2 3

2 3 0

2 1 4

2 1 3

 

 

Sample input 2

Sample output 2

1 3

10 100

11 22 33 44 55 66 77 88 99 100

1 100 1 100 1 100 1 100 1 100

58 58 58 58 58 58 58 58 58 58

42 42 42 42 42 42 42 42 66 42

11 0 33 0 42 0 42 0 34 0

 

 

SOLUTION

mathematics

 

Algorithm analysis

The milling program consists of s steps. Let mij be cut off from the surface in column j (1 ≤ j ≤ x) at the i-th (1 ≤ i ≤ s) milling step. Then it is obvious that in total in column j will be cut off max(m1j, m2j, …, msj). A milling scheme is a set of integers (cuts1, cuts2, …, cutsx), where

cutsj = max(m1j, m2j, …, msj), 1 ≤ j ≤ x

 

The same milling pattern applies to all w workpieces. After computing the cutsj (1 ≤ j ≤ x) values, apply the milling scheme to each part.

 

Algorithm realization

Declare the arrays. The information about workpieces will be stored in the array detail. The milling scheme will be stored in array cuts.

 

int detail[10001][101], cuts[101];

 

Read the input data.

 

scanf("%d %d %d %d", &w, &s, &x, &y);

 

Read the information about w workpieces.

 

for (i = 0; i < w; i++)

for (j = 0; j < x; j++)

  scanf("%d", &detail[i][j]);

 

Read and process s steps in a milling program. cuts[j] will contain the deepest cut at position j.

 

for (i = 0; i < s; i++)

for (j = 0; j < x; j++)

{

  scanf("%d", &val);

  if (val > cuts[j]) cuts[j] = val;

}

 

The maximum possible workpiece height is y. The cutter head in position j is lowered to the depth cuts[j]. Therefore, in position j from the i-th workpiece, the height will remain equal to min(detail[i][j], y – cuts[j]).

 

for (i = 0; i < w; i++)

{

  for (j = 0; j < x; j++)

    printf("%d ", min(detail[i][j], y - cuts[j]));

  printf("\n");

}