Canadian Computing Competition: 2014 Stage 2, Day 1, Problem 1
Troy loves triangles. He especially likes counting triangles. He has an -by-
grid consisting of either
.
or #
characters. Help him count the number of triangles formed only by #
characters in the grid. Triangles are of the form
#
# ###
#, ###, #####, etc.
More formally, a triangle of height consists of
rows for some positive integer
. The
-th row contains
#
characters for . The rows are centred above each other so that they are symmetrical about a vertical line down their middle.
Input Specification
The first line contains the number (
) representing the size of the grid. The next
lines each contain
characters as described above.
You can assume that for test cases worth 20% of the marks, .
Output Specification
Output the number of triangles in the grid.
Sample Input
5
.....
.###.
.###.
#####
.....
Output for Sample Input
16
Explanation of Output for Sample Input
There are triangles of height one,
triangles of height two, and
triangle of height three.
Comments
https://dmoj.ca/problem/dwite12c5p3 ??!??!?!?!
N goes up to 2000 for this version, but 256 for the dwite version
Watch out for edge cases (literally)
badum tss