2004 : Pairs
Problem type : Batch
Time limit : 4.0 second(s)
Memory limit : 150 megabyte(s)
Problem type : Batch
Time limit : 4.0 second(s)
Memory limit : 150 megabyte(s)
เมอโก และสลาฟโก ต้องการจะเล่นเกมด้วยกัน ก่อนอื่นพวกเขาจะต้องเลือกกระดานเกมชนิดใดชนิดหนึ่ง จากสามชนิดดังปรากฎในรูปวาดข้างล่าง
กระดานเกมทุกชนิดประกอบด้วยช่อง (แสดงด้วยวงกลมในรูปวาด) วางเรียงเป็นลักษณะตารางหนึ่ง สอง หรือสามมิติตามแต่ชนิดของตาราง จากนั้นเมอโกจะสามารถวางตุ๊กตาสัตว์ตัวจิ๋วจำนวน N ตัวลงในช่องต่าง ๆ
ระยะห่าง (distance) ระหว่างช่องสองช่องใดๆ บนกระดานเกม คือจำนวนก้าวน้อยที่สุด ที่ตุ๊กตาสัตว์ต้องใช้ เพื่อจะเคลื่อนที่จากช่องหนึ่งไปให้ถึงอีกช่องหนึ่ง โดยแต่ละก้าว คือการที่ตุ๊กตาสัตว์เคลื่อนที่ไปยังช่องที่ติดกัน (ที่มีเส้นเชื่อมตามรูปวาด)
ตุ๊กตาสัตว์สองตัว สามารถได้ยินเสียงกันและกันได้ ถ้าระยะห่างระหว่างช่องที่ตุ๊กตาสัตว์สองตัวอยู่ ไกลกันไม่เกินระยะห่าง D
งานของสลาฟโก คือการคำนวณหาว่า มีตุ๊กตาสัตว์กี่คู่ ที่สามารถได้ยินเสียงกันและกันได้
โจทย์
จงเขียนโปรแกรม เพื่อรับข้อมูล ชนิดของกระดานเกม ตำแหน่งของตุ๊กตาสัตว์ทั้งหมด และจำนวนเต็ม D แล้วคำนวณหาจำนวนคู่ของสัตว์บนกระดานนี้
ข้อมูลนำเข้า
บรรทัดแรกของข้อมูลป้อนเข้า มีจำนวนเต็มสี่จำนวนตามลำดับต่อไปนี้
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
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้
กระดานเกมทุกชนิดประกอบด้วยช่อง (แสดงด้วยวงกลมในรูปวาด) วางเรียงเป็นลักษณะตารางหนึ่ง สอง หรือสามมิติตามแต่ชนิดของตาราง จากนั้นเมอโกจะสามารถวางตุ๊กตาสัตว์ตัวจิ๋วจำนวน N ตัวลงในช่องต่าง ๆ
ระยะห่าง (distance) ระหว่างช่องสองช่องใดๆ บนกระดานเกม คือจำนวนก้าวน้อยที่สุด ที่ตุ๊กตาสัตว์ต้องใช้ เพื่อจะเคลื่อนที่จากช่องหนึ่งไปให้ถึงอีกช่องหนึ่ง โดยแต่ละก้าว คือการที่ตุ๊กตาสัตว์เคลื่อนที่ไปยังช่องที่ติดกัน (ที่มีเส้นเชื่อมตามรูปวาด)
ตุ๊กตาสัตว์สองตัว สามารถได้ยินเสียงกันและกันได้ ถ้าระยะห่างระหว่างช่องที่ตุ๊กตาสัตว์สองตัวอยู่ ไกลกันไม่เกินระยะห่าง D
งานของสลาฟโก คือการคำนวณหาว่า มีตุ๊กตาสัตว์กี่คู่ ที่สามารถได้ยินเสียงกันและกันได้
โจทย์
จงเขียนโปรแกรม เพื่อรับข้อมูล ชนิดของกระดานเกม ตำแหน่งของตุ๊กตาสัตว์ทั้งหมด และจำนวนเต็ม D แล้วคำนวณหาจำนวนคู่ของสัตว์บนกระดานนี้
ข้อมูลนำเข้า
บรรทัดแรกของข้อมูลป้อนเข้า มีจำนวนเต็มสี่จำนวนตามลำดับต่อไปนี้
- ชนิดของตาราง B (1 ≤ B ≤ 3)
- จำนวนสัตว์ N (1 ≤ N ≤ 100 000)
- ระยะ D ซึ่งเป็นระยะที่สัตว์สองตัวได้ยินถึงกัน (1 ≤ D ≤ 100 000 000)
- ขนาดของกระดาน M (ค่าพิกัดสูงสุดที่ยอมให้ปรากฎในข้อมูลนำเข้า)
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 |
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้
กำลังออนไลน์: 26 ผู้เยี่ยมชมและ 0 สมาชิก (0 บอท)