程式解題社網站 程式解題社網站上線了！
NTUCPC OJ 現在支援 Rust ！
NTUCPCPC 2026 初賽 & 決賽題目已公開！ 連結
YTP 2026 題目已公開！ 連結
1512 . 五維西洋棋
TopCoder
Tags
Description
最近，在擅長時間穿隧的昨日旅行機長（Yesterday Travel Pilot, 簡稱 YTP）們中流行起了一個復古的遊戲：有多重宇宙時間穿隧的五維西洋棋（5D Chess with Multiverse Time Travel）。
因為多重宇宙與時間穿隧已經不再是一個新奇的概念，YTP 們將這兩個元素移除，並加入了自己的變體規則。在這個變體規則中，棋盤變成無限大了，每隻棋子的座標改成用一個五維整數組 $(a, b, c, d, e)$ 表示。同時，又加入了一個新的棋子，稱為老虎。老虎是一個很強大的棋子，對於一隻位於 $(a, b, c, d, e)$ 的老虎而言，他可以攻擊所有座標位於滿足 $\max(\lvert a - a' \rvert, \lvert b - b' \rvert, \lvert c - c' \rvert, \lvert d - d' \rvert, \lvert e - e' \rvert) \le k$ 的 $(a', b', c' , d', e')$ 的棋子。其中，$k$ 是一個遊戲開始時大家約定好的常數。
正如西洋棋裡棋藝精湛，並達到特定要求者會被冠上特級大師（Grandmaster）的稱號，對於使用老虎這個棋子特別擅長者也會被冠上特級老虎（Grandtiger）的稱號。而想要成為特級老虎的一員，你必須要能夠快速看出老虎們的攻擊範圍，為此你做的特訓如下：
在棋盤上擺 $n$ 隻老虎，第 $i$ 隻老虎的座標為 $(a_i, b_i, c_i, d_i, e_i)$，並決定好 $k$。計算有多少對老虎 $(i, j), i < j$ 滿足第 $i$ 隻老虎與第 $j$ 隻老虎互相攻擊呢？也就是說有多少對 $(i, j), i < j$，滿足 $\max(\lvert a_i - a_j \rvert,\lvert b_i - b_j \rvert,\lvert c_i - c_j \rvert,\lvert d_i - d_j \rvert,\lvert e_i - e_j \rvert) \le k$。
Input Format
第一行有兩個整數 $n, k$，分別代表老虎的數量與約定好的常數 $k$。
接下來有 $n$ 行，第 $i$ 行有五個整數 $a_i\ b_i\ c_i\ d_i\ e_i$，代表第 $i$ 隻老虎的座標。
同一格上可能有多隻老虎。
- $1 \le n \le 10^ 5$
- $0 \le k \le 2 \times 10^ 9$
- $-10^ 9 \le a_i, b_i, c_i, d_i, e_i \le 10^ 9$
Output Format
輸出一行一個整數，代表互相攻擊的老虎對數。
Sample Input 1
4 1 0 0 0 0 0 1 1 1 1 1 2 2 2 2 2 0 0 0 0 5
Sample Output 1
2
Sample Input 2
3 2000000000 -1000000000 -1000000000 -1000000000 -1000000000 -1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 0 0 0 0 0
Sample Output 2
3
Hints
範測 1 解釋：
$k = 1$，四隻老虎中互相攻擊的有兩對：
- 第 $1$ 隻與第 $2$ 隻，五個維度的座標差都是 $1$。
- 第 $2$ 隻與第 $3$ 隻，五個維度的座標差都是 $1$。
其餘的四對座標差的最大值都超過 $1$。例如第 $1$ 隻與第 $4$ 隻在第五個維度上差了 $5$。
範測 2 解釋：
$k = 2 \times 10^ 9$，三隻老虎兩兩之間座標差的最大值分別為 $2 \times 10^ 9$、$10^ 9$、$10^ 9$，都不超過 $k$，所以三對都互相攻擊。
Problem Source
2026 YTP 高中組決賽 p11
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測試資料 | 0 |
| 2 | 2~12 | $n \le 2000$ | 4 |
| 3 | 0~24 | 無額外限制 | 16 |