2013 : Pyramid Base
Problem type : Batch
Time limit : 5.0 second(s)
Memory limit : 256 megabyte(s)

คุณได้รับการขอร้องให้หาพื้นที่ขนาดใหญ่ที่สุดเพื่อสร้างปิรามิดแห่งใหม่ตามงบประมาณที่มีให้ เพื่อเป็นข้อมูลประกอบการตัดสินใจ คุณได้รับข้อมูลสำรวจเกี่ยวกับพื้นที่ที่มีอยู่ในรูปตารางขนาด M´N เซลล์ แต่ละเซลล์เป็นพื้นที่สี่เหลี่ยมจัตุรัส ฐานของปิรามิดต้องเป็นสี่เหลี่ยมจัตุรัสเช่นกันโดยมีด้านทุกด้านขนานกับเส้นในตาราง

จากการสำรวจพื้นที่พบว่ามีสิ่งกีดขวางอยู่ P ก้อนซึ่งอาจซ้อนทับกัน แทนด้วยสี่เหลี่ยมในตารางซึ่งด้านทุกด้านขนานกับเส้นในตาราง พื้นที่ที่จะใช้เป็นฐานปิรามิดได้นั้นต้องปราศจากสิ่งกีดขวางใด ๆ   โดยการทำลายสิ่งกีดขวางก้อนที่ i ต้องใช้ค่าใช้จ่าย Ci และการทำลายสิ่งกีดขวางก้อนใดจะต้องทำลายทั้งก้อน นั่นหมายความว่าคุณไม่สามารถทำลายสิ่งกีดขวางใดเพียงบางส่วนได้ ขอให้ทราบว่าการทำลายสิ่งกีดขวางที่ทับซ้อนกับก้อนอื่นจะไม่มีผลต่อสิ่งกีดขวางก้อนอื่น ๆ เหล่านั้น

โจทย์

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

เงื่อนไขและการให้คะแนน

โปรแกรมของคุณจะถูกตรวจด้วยชุดทดสอบสามชุดที่แยกจากกัน ในทุกชุดทดสอบจะมีเงื่อนไขต่อไปนี้

1 M, N 1,000,000             ขนาดของตาราง

1 Ci 7,000                          ค่าใช้จ่ายในการทำลายสิ่งกีดขวางก้อนที่ i

1 Xi1 Xi2 M                      พิกัดในแกน X ของช่องซ้ายสุดและขวาสุดของสิ่งกีดขวางที่ i ตามลำดับ

1 Yi1 Yi2 N                       พิกัดในแกน Y ของช่องล่างสุดและบนสุดของสิ่งกีดขวางที่ i ตามลำดับ

ชุดทดสอบชุดแรก คะแนนรวม 35 คะแนน

B = 0                                       งบประมาณที่มี (นั่นคือคุณไม่มีงบที่จะทำลายสิ่งกีดขวางก้อนใดได้เลย)

1 P 1,000                           จำนวนก้อนของสิ่งกีดขวางในตาราง

ชุดทดสอบที่สอง คะแนนรวม 35 คะแนน

0 < B 2,000,000,000          งบประมาณที่มี

1 P 30,000                        จำนวนก้อนของสิ่งกีดขวางในตาราง

ชุดทดสอบที่สาม คะแนนรวม 30 คะแนน

B = 0                                       งบประมาณที่มี (นั่นคือคุณไม่มีงบที่จะทำลายสิ่งกีดขวางก้อนใดได้เลย)

1 P 400,000                      จำนวนก้อนของสิ่งกีดขวางในตาราง

ข้อมูลนำเข้า

โปรแกรมต้องอ่านข้อมูลจาก standard input ดังนี้

·        บรรทัดที่ 1 ประกอบด้วยจำนวนเต็มสองตัวคั่นด้วยช่องว่างหนึ่งช่อง ซึ่งก็คือ M และ N ตามลำดับ

·        บรรทัดที่ 2 ประกอบด้วยจำนวนเต็ม B แทนงบประมาณที่มี

·        บรรทัดที่ 3 ประกอบด้วยจำนวนเต็ม P แทนจำนวนสิ่งกีดขวางที่พบในการสำรวจ

·    P บรรทัดถัดมา แต่ละบรรทัดอธิบายรายละเอียดของสิ่งกีดขวางแต่ละก้อน โดยบรรทัดที่ i ของข้อมูลชุดนี้อธิบายสิ่งกีดขวางก้อนที่ i ภายในบรรทัดประกอบด้วยจำนวนเต็ม 5 จำนวนคั่นด้วยช่องว่างหนึ่งช่องคือ Xi1, Yi1, Xi2, Yi2, และ Ci ซึ่งแทนพิกัดช่องล่างซ้ายของสิ่งกีดขวาง พิกัดช่องบนขวาของสิ่งกีดขวาง และค่าใช้จ่ายในการทำลายสิ่งกีดขวางนั้น ๆ ตามลำดับ พิกัดของช่องล่างซ้ายสุดของพื้นที่คือ (1,1) และพิกัดของช่องบนขวาสุดของพื้นที่คือ (M,N)

ข้อมูลส่งออก

โปรแกรมต้องแสดงผลลัพธ์เป็นจำนวนเต็มเพียงจำนวนเดียวออกทาง standard output จำนวนเต็มนี้แสดงถึงความยาวด้านของฐานปิรามิดที่ยาวที่สุดที่เป็นไปได้ หากไม่สามารถหาพื้นที่เพื่อสร้างปิรามิดได้เลยให้โปรแกรมแสดงผลลัพธ์เป็นตัวเลข 0

อธิบายตัวอย่างที่หนึ่ง (ด้านล่าง)

 

รูปด้านบนแสดงตำแหน่งฐานปิรามิดที่เป็นไปได้สองตำแหน่ง ทั้งคู่ต่างก็มีความยาวด้านเท่ากับ 4

อธิบายตัวอย่างที่สอง (ด้านล่าง)

 

รูปด้านบนแสดงตำแหน่งที่เป็นไปได้เพียงตำแหน่งเดียว โดยมีความยาวด้านเท่ากับ 3

 

ที่มา: 20th International Olympiad in Informatics; Cairo, Egypt (Day 2)
ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
6 9
42
5
4 1 6 3 12
3 6 5 6 9
1 3 3 8 24
3 8 6 9 21
5 1 6 2 20
4
13 5
0
8
8 4 10 4 1
4 3 4 4 1
10 2 12 2 2
8 2 8 4 3
2 4 6 4 5
10 3 10 4 8
12 3 12 4 13
2 2 4 2 21
3

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

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