Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 1 megabyte(s)
โรงงานคุโรมาตี้ (แทนด้วยตัวอักษรเอ็กซ์พิมพ์ใหญ่ ‘X’) ต้องการขนส่งสินค้าไปยังลูกค้า (แทนด้วยตัวอักษรวายพิมพ์ใหญ่ ‘Y’) ซึ่งอยู่ห่างไกล มีถนนจากโรงงานไปหาลูกค้าเพียงหนึ่งเส้น ในระหว่างเส้นทางขนส่งจะมีจุดถ่ายสินค้าอยู่ M จุด (1 ≤ M ≤ 26) แทนด้วยตัวอักษรภาษาอังกฤษพิมพ์เล็ก ‘a’ … ‘z’ เมื่อรถบรรทุกสินค้าเดินทางมาถึงจุดถ่ายสินค้าต้องขนสินค้าใส่รถคันใหม่ เพื่อส่งไปยังสถานีถัดไป รถที่ประจำอยู่ที่โรงงานและแต่ละสถานีมีจำนวน P คัน (1 ≤ P ≤ 10) โดยไม่จำเป็นต้องเท่ากัน และแต่ละคันมีค่าใช้จ่ายในการขนส่งต่างกัน ยกตัวอย่างเช่น ในรูปที่ 1 จากสถานี a ไปสถานี b มีรถประจำสถานีอยู่ 2 คัน (P = 2) ในขณะที่จากสถานี b ไปยังลูกค้า (Y) จะมีรถประจำสถานีอยู่ 3 คัน (P = 3) สำหรับรถแต่ละคันจากสถานี a ไปยังสถานี b มีค่าใช้จ่ายเป็น 1 และ 4 หน่วย
ค่าใช้จ่ายสุทธิ (Cost) ในการขนส่งสินค้าระหว่างสถานีถ่ายโอนนั้น จะมีค่าเท่ากับ มัธยฐาน (Median) ของค่าใช้จ่ายของรถแต่ละคันประจำสถานีนั้น เจ้าของโรงงานจะได้รับข้อมูลค่าใช้จ่ายของรถแต่ละคัน ดังตัวอย่าง
|
X a 1 a X 7 a b 4 b a 1 b Y 3 b Y 2 Y b 6 ข้อมูลค่าใช้จ่ายของรถแต่ละคันประจำสถานี |
แผนผังเส้นทางและตำแหน่งของสถานีที่สมมูลกับรายงานด้านซ้ายมือ |
รูปที่ 1 ตัวอย่างข้อมูลค่าใช้จ่ายของรถแต่ละคันประจำสถานี
จากตัวอย่างข้างต้นสามารถคำนวณค่าใช้จ่ายได้เป็นดังนี้
หมายเหตุ มัธยฐาน (Median) เป็นค่ากลางของข้อมูล โดยพิจารณาจากข้อมูลที่เรียงแล้วจำนวน n ตัว โดยถ้ามีข้อมูลเป็นจำนวนคี่ จะเป็นข้อมูลลำดับที่ (n+1)/2 แต่ถ้ามีข้อมูลเป็นจำนวนคู่ จะเป็นข้อมูลค่าเฉลี่ยเลขคณิตของข้อมูลลำดับที่ n/2 และ (n/2)+1 ตัวอย่างเช่น
Median (1, 2, 4, 3, 5) = 3
Median (9, 2, 4, 5, 8, 1) = (5 + 4)/2 = 4.5
งานของคุณ
จงเขียนโปรแกรมเพื่อคำนวณค่าใช้จ่ายในการขนส่งสินค้าสุทธิที่เกิดขึ้น
ข้อมูลนำเข้า
ข้อมูลบรรทัดแรก แสดงจำนวน N ซึ่งแทนจำนวนรถทั้งหมดที่ใช้ในการขนส่งของทุกๆ เส้นทาง (2 £ N £ 270)
ข้อมูลบรรทัดถัดมา จำนวน N บรรทัด แต่ละบรรทัดแสดงข้อมูลของรถแต่ละคัน โดยระบุ ชื่อสถานี (‘a’ … ‘z’) หรือ โรงงาน (‘X’) หรือ ลูกค้า (‘Y’) คู่ที่เส้นทางนั้นเชื่อมต่ออยู่ ตามด้วยค่าใช้จ่ายซึ่งเป็นจำนวนเต็มบวกของรถนั้นๆ C (1 ≤ C ≤ 20) (ชื่อสถานีสามารถเรียงสลับลำดับกับทิศทางของการขนส่งสินค้าจริงได้ เช่น a b และ b a หมายถึงเส้นทางเดียวกัน) โดยคั่นด้วยช่องว่าง
ข้อมูลส่งออก
ถ้าเส้นทางขาดหาย ไม่สามารถส่งสินค้าจาก X ไป Y ได้ให้แสดง ข้อมูลบรรทัดเดียว ด้วยข้อความ broken
ในกรณีที่สามารถส่งสินค้าได้ ให้แสดง ข้อมูลส่งออกรวมทั้งสิ้น M+2 บรรทัดใน M+1 บรรทัดแรก แสดงเส้นทางระหว่างสถานีหนึ่ง ไปยังสถานีถัดไป พร้อมกับค่าใช้จ่ายของเส้นทางนั้น แสดงเป็นทศนิยมหนึ่งตำแหน่ง โดยเริ่มจาก โรงงาน X อยู่บรรทัดแรก และลูกค้า Y อยู่บรรทัดสุดท้าย
ในบรรทัดที่ M+2 แสดงค่าใช้จ่ายในการขนส่งสินค้าสุทธิที่เกิดขึ้น เป็นเลขจำนวนจริง ความละเอียดถึงทศนิยมหนึ่งตำแหน่ง
ที่มา: การแข่งขันคอมพิวเตอร์โอลิมปิกสอวน.ครั้งที่ 4 ปี 2551 วันที่ 2
| ตัวอย่างข้อมูลนำเข้า | ตัวอย่างข้อมูลส่งออก |
| 6 X a 1 a b 4 b a 1 b Y 3 b Y 2 Y b 6 | X a 1.0 a b 2.5 b Y 3.0 6.5 |
| 3 X a 2 c b 3 b Y 3 | broken |
| 5 q Y 3 X a 1 a b 2 t b 4 q t 5 | X a 1.0 a b 2.0 b t 4.0 t q 5.0 q Y 3.0 15.0 |
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้