Milling machines#7714

Milling machines (Editorial)

The milling program consists of $s$ steps. Let at the $i$ -th step $(1 \leq i \leq s)$ (1 \le i \le s) a layer of thickness $m_{ij}$ m_{ij} be removed from the surface in column $j (1 \leq j \leq x)$ j~(1 \le j \le x). It is clear that the total amount removed in column $j$ will be

ma x (m_{1 j}, m_{2 j}, ..., m_{s j})

max(m_{1j}, m_{2j}, ..., m_{sj})

We’ll call the milling scheme the set of integers

(c u t s_{1}, c u t s_{2}, ..., c u t s_{x}),

(cuts_1, cuts_2, ..., cuts_x),

where

c u t s_{j} = ma x (m_{1 j}, m_{2 j}, ..., m_{s j}), 1 \leq j \leq x

cuts_j = max(m_{1j}, m_{2j}, ..., m_{sj}), 1 \le j \le x

The same milling scheme is applied to all $w$ workpieces. After computing the values of $c u t s_{j} (1 \leq j \leq x)$ cuts_j~(1 \le j \le x), this scheme is then applied sequentially to each workpiece.

Algorithm implementation

Declare the arrays. The information about the workpieces is stored in the array $d e t ai l$ , and the milling scheme is stored in the array $c u t s$ .

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

Read the input data.

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

Read the information about the $w$ workpieces.

for (i = 0; i < w; i++)
for (j = 0; j < x; j++)
  scanf("%d", &detail[i][j]);

Read and process the $s$ steps of the milling program. For each position $j$ , the value $c u t s [j]$ cuts[j] represents the maximum cutting depth achieved at any of the steps.

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 height of a workpiece is $y$ . The milling head at position $j$ is lowered to a depth of $c u t s [j]$ cuts[j]. Consequently, after milling, the remaining height of the $i$ -th workpiece at position $j$ will be equal to

min (d e t ai l [i] [j], y - c u t s [j]) .

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");
}