NKPAIRS - IOI07 Pairs

Giới hạn
  • Thời gian: 0.66s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

 

 

 

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

 

  • Người up: paulmcvn
  • Nguồn bài: IOI 2007 - Croatia