Cut the Ticket
National Olympiad — National round (2024 season)
Submission name: bilet.cpp
Problem summary
A ticket has N rows and 10 unit-square columns labeled 0 through 9. For each given digit d, the row’s squares from column 0 through d inclusive are marked. Split the ticket into marked left squares and unmarked right squares. Find the area and total boundary perimeter of each part; disconnected pieces contribute all their boundaries.
Input
N, then N digits separated by spaces.
Output
Two lines: area and perimeter of the marked part, then area and perimeter of the unmarked part.
Constraints
1 ≤ N ≤ 16; digits are in [0,9], including possible leading zero.
Worked example
An independently prepared example for this explanation.
Input
4 3 6 0 8
Output
21 38 19 32
Solution analysis
- Model the small ticket as a grid. In row i, a cell belongs to the marked part precisely when its column is at most digit[i]; even digit zero marks one square.
- For each part separately, count one area unit for every belonging square. Examine its four sides: a side contributes to the perimeter if the neighboring cell is outside the ticket or belongs to the other part.
- For digits 3,6,0,8, the marked row widths are 4,7,1,9, giving area 21. The remaining 19 cells form the other part. Exposed-edge counting yields perimeters 38 and 32, including every component automatically.
Why it works
Each unit square contributes exactly one to its part’s area. Each boundary edge has exactly one neighboring square of that part, so it is counted once; internal shared edges have two belonging neighbors and are not counted. Hence the computed areas and perimeters are exact.
Watch out. Column 0 is included, so marked width is digit+1. A row with digit 9 leaves no right-side cells. Count the perimeter of every disconnected component.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> digit(n);
for (int &value : digit) {
cin >> value;
}
const int dr[4] = {-1, 1, 0, 0};
const int dc[4] = {0, 0, -1, 1};
for (int part = 0; part < 2; part++) {
int area = 0, perimeter = 0;
for (int row = 0; row < n; row++) {
for (int column = 0; column < 10; column++) {
bool marked = column <= digit[row];
if (marked != (part == 0)) {
continue;
}
area++;
// Count only edges exposed to the outside or to the other part.
for (int direction = 0; direction < 4; direction++) {
int nextRow = row + dr[direction];
int nextColumn = column + dc[direction];
if (nextRow < 0 || nextRow >= n || nextColumn < 0 || nextColumn >= 10) {
perimeter++;
} else if ((nextColumn <= digit[nextRow]) != marked) {
perimeter++;
}
}
}
}
cout << area << ' ' << perimeter << '\n';
}
}