CCO '14 P1 - Troyangles - Olympiads Online Judge

CCO '14 P1 - Troyangles

View as PDF

Submit solution

All submissions

Best submissions

Points: 10 (partial)

Time limit: 1.0s

Memory limit: 1G

Problem types

Canadian Computing Competition: 2014 Stage 2, Day 1, Problem 1

Troy loves triangles. He especially likes counting triangles. He has an $N$ ~N~-by- $N$ ~N~ 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 $h$ ~h~ consists of $h$ ~h~ rows for some positive integer $h$ ~h~. The $i$ ~i~-th row contains $2i - 1$ ~2i - 1~ # characters for $i = 1, \dots, h$ ~i = 1, \dots, h~. 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 $N$ ~N~ ( $1 \le N \le 2000$ ~1 \le N \le 2000~) representing the size of the grid. The next $N$ ~N~ lines each contain $N$ ~N~ characters as described above.

You can assume that for test cases worth 20% of the marks, $N \le 50$ ~N \le 50~.

Output Specification

Output the number of triangles in the grid.

Sample Input

5
.....
.###.
.###.
#####
.....

Output for Sample Input

Explanation of Output for Sample Input

There are $11$ ~11~ triangles of height one, $4$ ~4~ triangles of height two, and $1$ ~1~ triangle of height three.

Comments

22

AvidDay commented on Aug. 1, 2018, 6:19 p.m.

https://dmoj.ca/problem/dwite12c5p3 ??!??!?!?!

5

Jerry_Gu commented on Nov. 20, 2018, 10:27 p.m.

N goes up to 2000 for this version, but 256 for the dwite version

14

Akababa commented on May 10, 2017, 2:04 p.m.

Watch out for edge cases (literally)

3

Plasmatic commented on Jan. 31, 2019, 4:54 p.m.

badum tss