NKPAIRS - IOI07 Pairs

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/nkpairs


Mirko và Slavko chơi trò các con thú đồ chơi. Đầu tiên, Mirko và Slavko chọn một trong 3 bàn cờ như hình dưới đây. Mỗi bàn cờ bao gồm các ô (dưới dạng hình tròn trong hình vẽ) sắp xếp trên một lưới 1, 2 hoặc 3 chiều.

Sau đó Mirko sẽ đặt N con thú đồ chơi lên các ô.

Khoảng cách giữa 2 ô là số bước đi nhỏ nhất để một con thú đi từ ô này đến ô kia. Trong mỗi bước đi. con thú có thể bước đến 1 trong 4 ô kề với nó (nối với nhau bằng đoạn thẳng trong hình vẽ).

Hai con thú có thể nghe thấy nhau nếu khoảng cách giữa 2 ô chúng đứng không vượt quá D. Nhiệm vụ của Slavko là tính số cặp con thú có thể nghe thấy nhau.

Dữ liệu

Dòng đầu tiên chứa 4 số nguyên dương theo thứ tự:

  • Loại bàn cờ B (1 ≤ B ≤ 3).
  • Số con thú N (1 ≤ N ≤ 100000).
  • Khoảng cách lớn nhất D mà hai con thú có thể nghe thấy nhau (1 ≤ D ≤ 100000000).
  • Kích thước bàn cờ M (tọa độ lớn nhất xuất hiện trong dữ liệu).
    • Khi B=1, M không vượt quá 75000000.
    • Khi B=2, M không vượt quá 75000.
    • Khi B=3, M không vượt quá 75.

Mỗi dòng trong số N dòng sau chứa B số nguyên cách nhau bởi khoảng trắng, cho biết các tọa độ của một con thú đồ chơi. Mỗi tọa độ sẽ thuộc phạm vi [1, M]. Có thể có nhiều con thú nằm trên cùng 1 ô.

Kết qủa

Gồm 1 số nguyên duy nhất là số lượng con thú có thể nghe thấy nhau.

Lưu ý: sử dụng số nguyên 64-bit để tính kết quả (long long trong C/C++, int64 trong Pascal).

Hạn chế

 

Ví dụ

Dữ liệu:
1 6 5 100
25
50
50
10
20
23

Kết qủa
4

Dữ liệu:
2 5 4 10
5 2
7 2
8 4
6 5
4 4

Kết qủa
8

Dữ liệu:
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

Kết qủa
12


Được gửi lên bởi:Jimmy
Ngày:2007-12-18
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:IOI 2007 - Croatia

hide comments
2019-09-26 23:08:37
Hint :
Thử chuyển |xi - xj| + |yi - yj| về dạng khác xem :v

Last edit: 2019-09-28 07:12:11
2016-10-02 07:10:05
BIT 3D :))
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.