1068 : ล้อมกรอบ (border)
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 16 megabyte(s)
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 16 megabyte(s)
กำหนดตารางขนาด N คูณ N (1 ≤ N ≤ 100) โดยที่ขอบของตารางแต่ละขอบมีเลขเขียนกำกับเอาไว้ เช่น
เราต้องการล้อมกรอบพื้นที่จำนวน K (1 ≤ K ≤ N2) ช่อง เช่น ถ้า K = 5 วิธีหนึ่ง ที่อาจจะล้อมกรอบพื้นที่เป็นดังต่อไปนี้
การล้อมกรอบต้องเสียค่าใช้จ่าย ซึ่ง เราสามารถคำนวณค่าใช้จ่ายได้ตามขั้นตอนต่อไปนี้
1. จำแนกขอบที่ล้อมกรอบบริเวณ K ช่องดังกล่าว (ขอบเส้นหนาในรูปข้างบน) ออกเป็นสี่ชนิด ได้แก่
- ขอบบน คือ ขอบแนวนอนที่อยู่บนสุดของตาราง หรือช่องที่อยู่ใต้มันเป็นช่องที่ถูกล้อมกรอบ และช่องที่อยู่เหนือมันเป็นช่องที่ไม่ถูกล้อมกรอบ ในตัวอย่างคือขอบที่มีหมายเลข 70, 9, 30, และ 1
- ขอบล่าง คือ ขอบแนวนอนที่อยู่ล่างสุดของตาราง หรือช่องที่อยู่เหนือมันเป็นช่องที่ถูกล้อมกรอบ และช่องที่อยู่ใต้มันเป็นช่องที่ไม่ถูกล้อมกรอบ ในตัวอย่างคือขอบที่มีหมายเลข 57, 10, 55, และ 45
- ขอบซ้าย คือ ขอบแนวตั้ง ที่อยู่ซ้ายสุดของตาราง หรือช่องที่อยู่ด้านขวาของมันเป็นช่องที่ถูกล้อมกรอบ และช่องที่อยู่ด้านซ้ายของมันเป็นช่องที่ไม่ถูกล้อมกรอบ ในตัวอย่างคือขอบที่มีหมายเลข 23, 39, และ 99
- ขอบขวา คือ ขอบแนวตั้ง ที่อยู่ขวาสุดของตาราง หรือช่องที่ทางด้านซ้ายของมันเป็นช่องที่ถูกล้อมกรอบ และช่องที่อยู่ด้านขวาของมันเป็นช่องที่ไม่ถูกล้อมกรอบ ในตัวอย่างคือ ขอบที่มีหมายเลข 37, 98, และ 48
2. ทำการคำนวณค่าใช้จ่ายโดยใช้สูตรต่อไปนี้
ค่าใช้จ่าย = 3xผลรวมเลขขอบบน + 5xผลรวมเลขขอบซ้าย - 3xผลรวมเลขขอบล่าง - 5xผลรวมเลขขอบขวา
ดังนั้น ค่าใช้จ่ายในการล้อมกรอบดังรูปข้างบนจึงมีค่าเท่ากับ
3x(70+9+23+30+1) + 5x(23+39+99) - 3x(57+10+55+45) - 5x(37+98+48) = -212
เราอาจจะล้อมพื้นที่ 5 ช่องได้อีกหนึ่ง วิธี คือ
โดยในกรณีนี้ค่าใช้จ่ายในการล้อมกรอบจะมีค่าเท่ากับ
3x(57+10+81) + 5x(42+14+85) - 3x(27+97+83) - 5x(98+29+53) = -372
งานของคุณ
จงเขียนโปรแกรมรับค่า N และ K พร้อมทั้งหมายเลขบนขอบทั้งหมดของตาราง แล้วคำนวณค่าใช้จ่ายที่น้อยที่สุดเท่าที่จะเป็นไปได้ในการล้อมกรอบพื้นที่ K ช่อง
ข้อมูลนำเข้า
บรรทัดแรก มีจำนวนเต็มบวก N และ K ซึ่งมีขอบเขตดังที่ได้กล่าวไปแล้วข้างต้น
ต่อมาอีก 2N+1 บรรทัด เป็นข้อมูลหมายเลขที่อยู่บนขอบ เรียงจากเหนือลงใต้และซ้ายไปขวา กล่าวคือ
ในบรรทัดที่ 1+i เมื่อ i เป็นเลขคู่จะมีตัวเลขอยู่ N ตัว แสดงหมายเลขของขอบแนวนอนเรียงจากซ้ายไปขวา
ในบรรทัดที่ 1+i เมื่อ i เป็นเลขคี่จะมีตัวเลขอยู่ N+1 ตัว แสดงหมายเลขของขอบแนวตั้งเรียงจากซ้ายไปขวา
หมายเลขบนขอบแต่ละหมายเลขเป็นจำนวนเต็มที่ไม่เป็นลบที่มีค่าไม่เกิน 10,000
ข้อมูลส่งออก
บรรทัดแรก พิมพ์ค่าใช้จ่ายที่น้อยที่สุดที่เป็นไปได้ในการล้อมกรอบพื้นที่ K ช่อง
ทีมา: การแข่งขัน YTOPC กุมภาพันธ์ 2552
| ตัวอย่างข้อมูลนำเข้า | ตัวอย่างข้อมูลส่งออก |
| 4 5 11 42 30 56 49 85 23 37 15 70 9 81 60 39 2 42 98 6 57 10 55 77 14 32 28 29 30 27 64 83 1 71 85 53 99 48 5 97 68 45 | -1170 |
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้
กำลังออนไลน์: 7 ผู้เยี่ยมชมและ 0 สมาชิก (0 บอท)