A Dotted Triangle
National Olympiad — Municipal round (2011 season)
Submission name: fig.cpp
Problem summary
Print a left-aligned triangle of n rows. Its boundary consists of stars and its interior of dots. Separate adjacent symbols by exactly one space.
Input
One integer n.
Output
The n-row triangle.
Constraints
3 < n < 20.
Worked example
An independently prepared example for this explanation.
Input
5
Output
* * * * . * * . . * * * * * *
Solution analysis
- Row r contains exactly r symbols. A symbol is on the boundary if it is the first or last in its row, or the row is the final row.
- For each position print a star on the boundary and a dot otherwise. Print a separator before every symbol except the first, avoiding trailing spaces.
- With n = 5, row 4 is * . . * because its two middle positions are internal. Row 5 contains only stars because it is the bottom edge.
Why it works
The nested loops visit exactly the positions of the triangular shape. The boundary condition identifies its left, right, and bottom edges, so each position receives the required star or dot. The separator rule places exactly one space between symbols.
Complexity: O(n²) time and O(1) extra space.
Watch out. The entire bottom row is boundary. Add spaces between symbols, not after the last symbol.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
for (int row = 1; row <= n; row++) {
for (int column = 1; column <= row; column++) {
if (column > 1) {
cout << ' ';
}
// The boundary consists of both sloping edges and the bottom row.
bool boundary = column == 1 || column == row || row == n;
cout << (boundary ? '*' : '.');
}
cout << '\n';
}
}