TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

100.0% (6/6)

Submission's AC Ratio

32.7% (16/49)

Tags

Description

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

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

兩個細格之間的距離定義為動物玩具從其中一格移動到另一細格的最少步驟。
在每一步驟,一個動物玩具可移到與其相鄰(在上圖中以線段連接)的細格。

有趣的是,這些玩具會發出叫聲,(仙女龍?!)(啊ˊˊ啊ˋˋ)
若兩個動物玩具的距離不超過 D 時,他們就可互相聽到對方的叫聲。
史拉可的目標如下:計算有多少組(pair)的動物玩具可以聽到互相的叫聲。

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

Input Format

以下三組sanple input將與sample output一一對應

input 1input 2input 3
1 6 5 100 25 50 50 10 20 23 2 5 4 10 5 2 7 2 8 4 6 5 4 4 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

Output Format

output 1output 2output 3
4812

Sample Input

輸入的第一行有四個整數如下所述:
‧ 選定的盤面 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 。

任何細格可以同時有一隻以上的動物玩具。

Sample Output

輸出一整數,即可以互相聽到叫聲的動物玩具組數。
注意:請用 64-位元整數運算及輸出結果 (C/C++: 用 long long, Pascal: 用 int64)。

Hints

Problem Source

原TIOJ1345 / IOI 2007, Day 2 problemsetter: kelvin

Subtasks

For Testdata: 0 ~ 0, Score: 3
For Testdata: 1 ~ 1, Score: 3
For Testdata: 2 ~ 2, Score: 3
For Testdata: 3 ~ 3, Score: 3
For Testdata: 4 ~ 4, Score: 3
For Testdata: 5 ~ 5, Score: 3
For Testdata: 6 ~ 6, Score: 3
For Testdata: 7 ~ 7, Score: 3
For Testdata: 8 ~ 8, Score: 3
For Testdata: 9 ~ 9, Score: 3
For Testdata: 10 ~ 10, Score: 3
For Testdata: 11 ~ 11, Score: 3
For Testdata: 12 ~ 12, Score: 3
For Testdata: 13 ~ 13, Score: 3
For Testdata: 14 ~ 14, Score: 3
For Testdata: 15 ~ 15, Score: 3
For Testdata: 16 ~ 16, Score: 3
For Testdata: 17 ~ 17, Score: 3
For Testdata: 18 ~ 18, Score: 3
For Testdata: 19 ~ 19, Score: 3
For Testdata: 20 ~ 20, Score: 3
For Testdata: 21 ~ 21, Score: 3
For Testdata: 22 ~ 22, Score: 3
For Testdata: 23 ~ 23, Score: 3
For Testdata: 24 ~ 24, Score: 3
For Testdata: 25 ~ 25, Score: 3
For Testdata: 26 ~ 26, Score: 3
For Testdata: 27 ~ 27, Score: 3
For Testdata: 28 ~ 28, Score: 3
For Testdata: 29 ~ 29, Score: 3
For Testdata: 30 ~ 30, Score: 3
For Testdata: 31 ~ 31, Score: 3
For Testdata: 32 ~ 32, Score: 4
No. Time Limit (ms) Memory Limit (KiB)
0 2000 150000
1 2000 150000
2 2000 150000
3 2000 150000
4 2000 150000
5 2000 150000
6 2000 150000
7 2000 150000
8 2000 150000
9 2000 150000
10 2000 150000
11 2000 150000
12 2000 150000
13 2000 150000
14 2000 150000
15 2000 150000
16 2000 150000
17 2000 150000
18 2000 150000
19 2000 150000
20 2000 150000
21 2000 150000
22 2000 150000
23 1999 150000
24 2000 150000
25 2000 150000
26 2000 150000
27 2000 150000
28 2000 150000
29 2000 150000
30 2000 150000
31 2000 150000
32 2000 150000