Problem : 256 - Pairs

Problem Statistics

Solved Member: 15　　Submission: 93　　User Tried: 15

Statement:

馬可 (Mirko) 和史拉可 (Slavko) 在玩動物玩具。首先，他們先從如下圖的三種遊戲盤面中選擇一種盤面類型。盤面上佈滿了一維、二維、或三維的細格（在圖中以圓圈代表之）。

接著馬可將N個動物玩具擺放到細格上。

兩個細格之間的距離定義為動物玩具從其中一格移動到另一細格的最少步驟。
在每一步驟，一個動物玩具可移到與其相鄰（在上圖中以線段連接）的細格。

若兩個動物玩具的距離不超過D時，他們就可互相聽到對方的叫聲。
史拉可的目標如下：計算有多少組(pair)的動物玩具可以聽到互相的叫聲。

Task:

請寫一個程式，當給定一種盤面、動物玩具的位置、及數字D時，計算出符合上述條件的組數。

Input:Output:

輸入的第一行有四個整數如下所述：
　　• 選定的盤面 B (1 ≤ B ≤ 3)；
　　• 動物玩具總數 N (1 ≤ N ≤ 100 000) ；
　　• 任意兩隻動物玩具可以互相聽到叫聲的最遠距離 D (1 ≤ D ≤ 100 000 000) ；
　　• 選定的盤面大小 M （輸入資料中最大的座標）：
　　　　• 當 B = 1時，M最大是 75 000 000.
　　　　• 當 B = 2時，M最大是 75 000.
　　　　• 當 B = 3時，M最大是 75.
接下來的N行每行都有B個整數，整數間以一個空白隔開，代表動物玩具的位置。座標值都介於1和 M (含)。
任何細格可以同時有一隻以上的動物玩具。

佔總分30分的測試資料中，每組動物玩具數N最多為1,000。
此外，如果正確的解出同一種盤面類型的所有測試資料，則將獲得至少30分。

輸出一整數，即可以互相聽到叫聲的動物玩具組數。

Sample Input:Sample Output:

Sample #1:
1 6 5 100
25
50
50
10
20
23

Sample #2:
2 5 4 10
5 2
7 2
8 4
6 5
4 4

Sample #3:
3 8 10 20
10 10 10
10 10 20
10 20 10
10 20 20
20 10 10
20 10 20
20 20 10
20 20 20

Sample #1:
4

Sample #2:
8

Sample #3:
12

HINT:

Sample #1的四組為:
• 1-5 (距離為 5)
• 1-6 (距離為2)
• 2-3 (距離為0)
• 5-6 (距離為3)

Sample #2的八組為:
• 1-2 (距離為2)
• 1-4 (距離為4)
• 1-5 (距離為3)
• 2-3 (距離為3)
• 2-4 (距離為4)
• 3-4 (距離為3)
• 3-5 (距離為4)
• 4-5 (距離為3)

Source:

IOI 2007

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0-1	1000ms	153600kb
0-2	1000ms	153600kb
0-3	1000ms	153600kb
1-1	1500ms	153600kb	5
1-2	1500ms	153600kb
2	1500ms	153600kb	5
3-1	1500ms	153600kb	7
3-2	1500ms	153600kb
4-1	1500ms	153600kb	8
4-2	1500ms	153600kb
5-1	1500ms	153600kb	8
5-2	1500ms	153600kb
5-3	1500ms	153600kb
6-1	1500ms	153600kb	10
6-2	1500ms	153600kb
7-1	1500ms	153600kb	8
7-2	1500ms	153600kb
8-1	1500ms	153600kb	8
8-2	1500ms	153600kb
8-3	1500ms	153600kb
8-4	1500ms	153600kb
9-1	1500ms	153600kb	8
9-2	1500ms	153600kb
9-3	1500ms	153600kb
9-4	1500ms	153600kb
10-1	1500ms	153600kb	10
10-2	1500ms	153600kb
11-1	1500ms	153600kb	7
11-2	1500ms	153600kb
11-3	1500ms	153600kb
12-1	1500ms	153600kb	8
12-2	1500ms	153600kb
12-3	1500ms	153600kb
13-1	1500ms	153600kb	8
13-2	1500ms	153600kb
13-3	1500ms	153600kb