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

內容

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

輸入說明

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

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

輸出說明

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

範例輸入 #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})$ 演算法	1493	2017-12-17 20:44