数三角形(Triangle)
小Q在纸上看到一个这样的等边三角形:等边三角形的每边长度为n,被分成n等份,于是每一条边就有n-1个等分点。而整个三角形被连接两个不同边的等分点且平行于三角形的第三边的线段分成了n2个单位等边三角形(边长为1)。下图左是n=5的情况:
小Q把其中的删掉其中的一些短边,小Q想知道,剩下的边一共组成了多少个三角形(包括所有m*m的三角形(1<=m<=n),正立的和倒立的都算,只要三角形的3m条短边都没有被删除就算是组成了一个三角形)。例如,上面的右图就有19个三角形。
[输入]
大三角形的所有短边可以看成是由(n+1)*n/2个单位三角形的边界组成。如右图的灰色三角形所示。其中第1排有一个灰色三角形,第2排有两个灰色三角形……第n排有n个灰色三角形。所以输入是这样的:
第一行有一个数n(1<=n<=1000)。
接下来的n行,第i行有i组数,每一组描述一个三角形,从左到右描述,一组数有3个数,非0即1,表示对应的边界是否被删除,0表示被删除了,1表示没有被删除,按照三角形的左、右、下边界描述。所以第i行有3i个数,每一个数是0或1。
[输出]
只有1行,表示有多少个三角形的边界都没有被删除。
[输入样例]
5
1 1 1
1 1 0 1 1 0
1 1 1 1 1 1 1 0 1
1 0 1 1 1 1 0 1 1 1 1 1
0 1 1 1 1 1 0 1 1 1 1 1 0 1 1
[输出样例]
19
[样例说明]
样例的图上面右图,其中,各种类型的三角形个数如下表:
1 2 3 4 5
正立 7 5 2 0 0
倒立 4 1 0 0 0