2004 : Pairs
Problem type : Batch
Time limit : 4.0 second(s)
Memory limit : 150 megabyte(s)
เมอโก และสลาฟโก ต้องการจะเล่นเกมด้วยกัน ก่อนอื่นพวกเขาจะต้องเลือกกระดานเกมชนิดใดชนิดหนึ่ง จากสามชนิดดังปรากฎในรูปวาดข้างล่าง


กระดานเกมทุกชนิดประกอบด้วยช่อง (แสดงด้วยวงกลมในรูปวาด) วางเรียงเป็นลักษณะตารางหนึ่ง สอง หรือสามมิติตามแต่ชนิดของตาราง จากนั้นเมอโกจะสามารถวางตุ๊กตาสัตว์ตัวจิ๋วจำนวน N ตัวลงในช่องต่าง ๆ

ระยะห่าง (distance) ระหว่างช่องสองช่องใดๆ บนกระดานเกม คือจำนวนก้าวน้อยที่สุด ที่ตุ๊กตาสัตว์ต้องใช้ เพื่อจะเคลื่อนที่จากช่องหนึ่งไปให้ถึงอีกช่องหนึ่ง โดยแต่ละก้าว คือการที่ตุ๊กตาสัตว์เคลื่อนที่ไปยังช่องที่ติดกัน (ที่มีเส้นเชื่อมตามรูปวาด)

ตุ๊กตาสัตว์สองตัว สามารถได้ยินเสียงกันและกันได้ ถ้าระยะห่างระหว่างช่องที่ตุ๊กตาสัตว์สองตัวอยู่ ไกลกันไม่เกินระยะห่าง D

งานของสลาฟโก คือการคำนวณหาว่า มีตุ๊กตาสัตว์กี่คู่ ที่สามารถได้ยินเสียงกันและกันได้

โจทย์
จงเขียนโปรแกรม เพื่อรับข้อมูล ชนิดของกระดานเกม ตำแหน่งของตุ๊กตาสัตว์ทั้งหมด และจำนวนเต็ม D แล้วคำนวณหาจำนวนคู่ของสัตว์บนกระดานนี้


ข้อมูลนำเข้า
บรรทัดแรกของข้อมูลป้อนเข้า มีจำนวนเต็มสี่จำนวนตามลำดับต่อไปนี้
  • ชนิดของตาราง B (1 ≤ B ≤ 3)
  • จำนวนสัตว์ N (1 ≤ N ≤ 100 000)
  • ระยะ D ซึ่งเป็นระยะที่สัตว์สองตัวได้ยินถึงกัน (1 ≤ D ≤ 100 000 000)
  • ขนาดของกระดาน M (ค่าพิกัดสูงสุดที่ยอมให้ปรากฎในข้อมูลนำเข้า)
o เมื่อ B = 1, M จะมีค่าไม่เกิน 75 000 000
o เมื่อ B = 2, M จะมีค่าไม่เกิน 75 000
o เมื่อ B = 3, M จะมีค่าไม่เกิน 75

ถัดจากนั้นไปอีก N บรรทัด แต่ละบรรทัดจะมีจำนวนเต็มบรรทัดละ B ตัว แต่ละตัวคั่นด้วยช่องว่าง ซึ่งแต่ละตัวคือตำแหน่งพิกัดในแต่ละแกนของตุ๊กตาสัตว์ตัวหนึ่ง โดยแต่ละจำนวนจะมีค่าตั้งแต่ 1 จนถึง M (รวม M)
ในแต่ละช่อง สามารถมีตุ๊กตาสัตว์มากกว่าหนึ่งตัวอยู่ด้วยกันได้

ข้อมูลส่งออก
ข้อมูลส่งออก จะมีจำนวนเต็มตัวเดียว แสดงจำนวนคู่ของตุ๊กตาสัตว์ ที่สามารถได้ยินเสียงกันและกันได้

หมายเหตุ: ให้ใช้ตัวแปรจำนวนเต็ม 64 บิตในการคำนวณคำตอบ (long long ในภาษา C/C++)

ที่มา: International Olympiad in Informatics 2007 Day 2
ZAGREB – CROATIA AUGUST 15 – 22
ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
1 6 5 100
25
50
50
10
20
23
4
2 5 4 10
5 2
7 2
8 4
6 5
4 4
8
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
12

ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้

กำลังออนไลน์: 16 ผู้เยี่ยมชมและ 1 สมาชิก (0 บอท)