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

內容

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

輸入說明

輸入的第一行為一個正整數$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}$。

輸出說明

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

範例輸入 #1

範例輸出 #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

提示：

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

標籤:

數學

出處:

編號	身分	題目	主題	人氣	發表日期
13146	xavier13540 (柊四千)	a858	$O(N^2)$演算法	1308	2017-12-17 20:44