DWITE '12 R5 #3 - Triangle Count - DMOJ: Modern Online Judge

DWITE '12 R5 #3 - Triangle Count

View as PDF

Submit solution

All submissions

Best submissions

Points: 7

Time limit: 1.0s

Memory limit: 64M

Problem type

DWITE, February 2013, Problem 3

A typical Q1 level problem is to draw some ASCII triangles. Well, after a bunch of students wrote their attempts, it's time to count the mess. Given a grid with some pattern, how many different triangles could it have been? The ASCII triangles have shapes such as:

Copy

        #
   #   ###
# ### ##### etc.

The input will contain 5 test cases. The first line of each case is a number $1 \le N \le 256$ $1 \leq N \leq 256$ representing the size of the square grid, followed by $N$ $N$ lines describing the grid.

The output will contain 5 lines of output, each a count of different triangles that could be counted. The orientation of the triangles is just as shown above, for the sake of simplicity. In the sample case below, there are $11$ $11$ triangles of size one, $4$ $4$ of size three, and $1$ $1$ of size five, for a total of $11+4+1=16$ $11 + 4 + 1 = 16$ (The ASCII pattern doesn't support triangles of even length.)

Sample Input

Copy

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

Sample Output

Copy

Problem Resource: DWITE

Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported

Comments

0

maxcruickshanks commented on Aug. 8, 2022, 4:57 p.m.

Since the original data were weak, an additional test case was added, and all submissions were rejudged.

0

7kxb commented on Aug. 6, 2022, 9:21 p.m.

test case too weak, you can check each cell's adjacent cells up to the 3rd triangle (5x3) and it would still AC