a858. 數三角形 - 高中生程式解題系統

Content

給定一個大小為$N$的完全圖，其中的每條邊可能是紅色或黑色。任三個不同的點都可以形成一個三角形，請問三邊同色的三角形有幾個？

Input

輸入的第一行為一個正整數$N$。接下來的$N$行，每行有$N$個數字，其中第$i$行的第$j$個數字$c_{ij}$代表邊$(i,j)$的顏色，紅色用$1$表示，黑色用$2$表示，而當$i=j$時則用$0$表示。

$3 \leq N \leq 1000$。
對於所有的$1 \leq i, j \leq N$，保證有$c_{ij}=c_{ji}$。

Output

請輸出同色三角形的數目。

Sample Input #1

Sample Output #1

測資資訊：

記憶體限制： 512 MB
不公開測資點#0 (20%): 0.2s , <1M
不公開測資點#1 (20%): 0.2s , <1M
不公開測資點#2 (20%): 0.2s , <10M
不公開測資點#3 (20%): 0.2s , <10M
不公開測資點#4 (20%): 0.2s , <10M

Hint ：

(2017-12-16 更新)
這是我比較早期的題目
由於當時出題經驗不足 $N$設太小讓一些$O(N^3)$的naïve做法AC了
只好降低時限並重測了@@
雖然還是可以把O(N^3)的code優化到在0.2s內跑完QAQ

Tags:

數學

出處:

ID	User	Problem	Subject	Hit	Post Date
13146	xavier13540 (柊四千)	a858	$O(N^2)$演算法	1437	2017-12-17 20:44