1345 . [IOI 2007, Day 2] Pairs
TopCoder
Description
馬可 (Mirko) 和史拉可 (Slavko) 在玩動物玩具。首先，他們先從如下圖的三種遊戲盤面中選擇一種盤面類型。
盤面上佈滿了一維、二維、或三維的細格（在圖中以圓圈代表之）。
接著馬可將 N 個動物玩具擺放到細格上。
兩個細格之間的距離定義為動物玩具從其中一格移動到另一細格的最少步驟。
在每一步驟，一個動物玩具可移到與其相鄰（在上圖中以線段連接）的細格。
有趣的是，這些玩具會發出叫聲，（仙女龍?!）(啊ˊˊ啊ˋˋ)
若兩個動物玩具的距離不超過 D 時，他們就可互相聽到對方的叫聲。
史拉可的目標如下：計算有多少組(pair)的動物玩具可以聽到互相的叫聲。
請寫一個程式，當給定一種盤面、動物玩具的位置、及數字 D 時，計算出符合上述條件的組數。
Input Format
輸入的第一行有四個整數如下所述：
‧ 選定的盤面 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 。
任何細格可以同時有一隻以上的動物玩具。
Output Format
輸出一整數，即可以互相聽到叫聲的動物玩具組數。
注意：請用 64-位元整數運算及輸出結果 (C/C++: 用 long long, Pascal: 用 int64)。
Sample Input 1
1 6 5 100 25 50 50 10 20 23
Sample Output 1
4
Sample Input 2
2 5 4 10 5 2 7 2 8 4 6 5 4 4
Sample Output 2
8
Sample Input 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 Output 3
12
Hints
Problem Source
原TIOJ1345 / IOI 2007, Day 2 problemsetter: kelvin
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 3 |
| 2 | 1 | 3 |
| 3 | 2 | 3 |
| 4 | 3 | 3 |
| 5 | 4 | 3 |
| 6 | 5 | 3 |
| 7 | 6 | 3 |
| 8 | 7 | 3 |
| 9 | 8 | 3 |
| 10 | 9 | 3 |
| 11 | 10 | 3 |
| 12 | 11 | 3 |
| 13 | 12 | 3 |
| 14 | 13 | 3 |
| 15 | 14 | 3 |
| 16 | 15 | 3 |
| 17 | 16 | 3 |
| 18 | 17 | 3 |
| 19 | 18 | 3 |
| 20 | 19 | 3 |
| 21 | 20 | 3 |
| 22 | 21 | 3 |
| 23 | 22 | 3 |
| 24 | 23 | 3 |
| 25 | 24 | 3 |
| 26 | 25 | 3 |
| 27 | 26 | 3 |
| 28 | 27 | 3 |
| 29 | 28 | 3 |
| 30 | 29 | 3 |
| 31 | 30 | 3 |
| 32 | 31 | 3 |
| 33 | 32 | 4 |