28. Wood Cutting – Solution
Figure 1: All pieces of wood on the belt, built from cubes, for example 1
These are only imagined cubes. Let us look at the input data for example 1:
4
4
1 1 0 0
1 1 0 0
1 1 0 0
1 1 0 0
0 0 1 0
1 1 1 0
1 1 1 0
1 1 1 0
0 1 0 0
1 1 0 0
1 1 0 0
0 0 0 0
0 0 0 0
1 1 1 0
1 0 1 0
0 0 0 0
The first number n=4 is the number of pieces on the belt, which is 4 in this example. The second number k=4 is the largest dimension of the matrix, i.e. the space in which one piece must fit, which in this case is a space of 16 cubes arranged in 4 rows and 4 columns. The pieces will not always fill this space completely, and the numbers in the 4x4 matrix, 0 or 1, say whether a given cube is filled with material or not (1 – yes, 0 – no). For example, we can see that the first piece filled two columns, while two are empty (the white squares). This is what the matrix says:
1 1 0 0
1 1 0 0
1 1 0 0
1 1 0 0
In this way we could, for example, count the cubes above and below the position of the saw (the horizontal line), and so count the amount of material below and above and find the difference.The algorithm
The task could be solved as described above: go through a loop in which the position of the saw changes, and in every iteration count how many cubes with material (value 1 in the matrix) there are above and how many below, and find their difference. Following the algorithm for finding the minimum value – in this example of the difference between the amounts above and below – after every iteration we check whether the new difference is smaller than the one found so far, and if it is, we update the minimum difference. To avoid counting the cubes again for every position, while reading the input we count how many cubes with material each row has (over all pieces). This can be done in the following way:#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<int> woodPerRow(k, 0); // The amount of wood in every row over all pieces
int total = 0;
for (int i = 0; i < n; i++) { // Every piece
for (int j = 0; j < k; j++) { // Every row in the piece
for (int l = 0; l < k; l++) { // Every column in the row
int x;
cin >> x;
if (x == 1) {
woodPerRow[j]++; // Add the wood to the matching row
total++;
}
}
}
}
// Now we can find the best position for the saw
int below = 0;
int above = total;
int minDiff = abs(above - below);
for (int i = 0; i < k; i++) { // Move the position of the saw through the rows
below += woodPerRow[i];
above = total - below;
int diff = abs(above - below);
if (diff < minDiff) {
minDiff = diff;
}
}
cout << minDiff << endl;
return 0;
}
For example 1 the program prints 0: the rows have 4, 10, 9 and 5 cubes of wood (28 in total), and the saw between the second and the third row divides them into 14 and 14.
- Input and initialization:
- At the beginning the program reads the numbers n and k, which are the number of pieces of wood and the size of every piece (the dimensions of the matrix).
- We create the vector woodPerRow, which will hold the number of cubes with wood in every row (over all pieces), and the variable total for the total amount of wood.
- Reading the wood and counting the pieces:
- The program uses three nested loops: over the pieces, over the rows of a piece and over the columns of a row.
- For every 1 that is read, it increases the counter of the row in which it is (woodPerRow[j]) and the total amount (total).
- Placing the saw and computing the difference:
- At the beginning all the wood is on one side (above = total, below = 0).
- The loop moves the saw row by row, updates the amount of wood on both sides and computes the absolute difference between those two values.
- Finding the best position of the saw:
- For every position the program computes the current difference between the wood below and above (diff), and the smallest value of that difference (minDiff) is the optimal solution.
