1008 : Skyline
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 64 megabyte(s)
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 64 megabyte(s)
รัฐบาลวางแผนสร้างเมืองใหม่บนพื้นที่ราบที่มีระดับเสมอกัน โดยกำหนดให้อาคารที่จะสร้างแต่ละหลังมีรูปทรงเป็นสี่เหลี่ยมผืนผ้า หลังจากที่มีการสร้างอาคารแล้วเมื่อมองตัวเมืองจากระยะไกล จะเห็นเส้นขอบฟ้าตามแนวเส้นขอบของอาคาร และทุกครั้งที่มีการสร้างอาคารเพิ่มขึ้น เส้นขอบฟ้าของตัวเมืองจะเปลี่ยนแปลงไป
อาคารที่จะสร้างขึ้นแต่ละหลัง กำหนดด้วยจำนวนเต็มบวกสามจำนวนคือ ( Li , Hi , Ri ) เมื่อ Li และ Ri เป็นตำแหน่งตามแกนนอนด้านซ้ายและขวาของอาคารลำดับที่ i ตามลำดับ ส่วน Hi เป็นความสูงของอาคารนั้น เช่น (1, 11, 5) หมายถึง อาคารที่สร้างขึ้นโดยมีขอบด้านซ้ายอยู่ที่ตำแหน่งที่ 1 ขอบด้านขวาอยู่ที่ตำแหน่งที่ 5 ของแกนนอน และมีความสูงเป็น 11 หน่วย เมื่อสร้างอาคารนี้เสร็จจะได้เส้นขอบฟ้าใหม่เป็น (1, 11, 5, 0) นั่นคือ ที่ตำแหน่งที่ 1 ขอบฟ้ายกขึ้นสูง 11 หน่วยตามความสูงของอาคารไปจนถึงตำแหน่งที่ 5 แล้วความสูงลดลงเป็น 0
จงเขียนโปรแกรมคำนวณหาเส้นขอบฟ้าจากข้อมูลของอาคารที่กำหนดให้ และแสดงผล
ข้อมูลนำเข้า
1. บรรทัดแรกเป็นจำนวนอาคารที่ต้องการหาเส้นขอบฟ้า มีค่าตั้งแต่ 1 ถึง 3,000
2. บรรทัดต่อไปแต่ละบรรทัดเป็นข้อมูลของอาคารแต่ละหลังในรูปแบบ Li Hi Ri โดยแต่ละตัวมีค่าตั้งแต่ 1 ถึง 255
3. ระหว่างข้อมูลแต่ละตัวในข้อ ๒. คั่นด้วยเว้นวรรค 1 วรรค
ข้อมูลส่งออก
1. ผลลัพธ์ของโปรแกรมมีเพียงบรรทัดเดียว ได้แก่ เส้นขอบฟ้าที่เกิดจากข้อมูลของอาคารที่เป็นข้อมูลนำเข้า โดยเส้นขอบฟ้ามีรูปแบบดังนี้ v1 v2 v3 … vn-2 vn-1 vn เมื่อ i เป็นจำนวนคี่ vi จะแทนตำแหน่งของเส้นขอบฟ้าตามแกนนอน และ เมื่อ i เป็นจำนวนคู่ v i แทนความสูงของเส้นขอบฟ้าที่ตำแหน่งนั้น ด้วยเหตุนี้ vn จึงมีค่าเป็น 0 เนื่องจากเส้นขอบฟ้าลดลงสู่ระดับพื้น
2. ผลลัพธ์แต่ละจำนวนให้คั่นด้วยเว้นวรรค 1 วรรค
ที่มา: การแข่งขันคอมพิวเตอร์โอลิมปิก สอวน. ครั้งที่ 2 มหาวิทยาลัยบูรพา
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้
อาคารที่จะสร้างขึ้นแต่ละหลัง กำหนดด้วยจำนวนเต็มบวกสามจำนวนคือ ( Li , Hi , Ri ) เมื่อ Li และ Ri เป็นตำแหน่งตามแกนนอนด้านซ้ายและขวาของอาคารลำดับที่ i ตามลำดับ ส่วน Hi เป็นความสูงของอาคารนั้น เช่น (1, 11, 5) หมายถึง อาคารที่สร้างขึ้นโดยมีขอบด้านซ้ายอยู่ที่ตำแหน่งที่ 1 ขอบด้านขวาอยู่ที่ตำแหน่งที่ 5 ของแกนนอน และมีความสูงเป็น 11 หน่วย เมื่อสร้างอาคารนี้เสร็จจะได้เส้นขอบฟ้าใหม่เป็น (1, 11, 5, 0) นั่นคือ ที่ตำแหน่งที่ 1 ขอบฟ้ายกขึ้นสูง 11 หน่วยตามความสูงของอาคารไปจนถึงตำแหน่งที่ 5 แล้วความสูงลดลงเป็น 0
จงเขียนโปรแกรมคำนวณหาเส้นขอบฟ้าจากข้อมูลของอาคารที่กำหนดให้ และแสดงผล
ข้อมูลนำเข้า
1. บรรทัดแรกเป็นจำนวนอาคารที่ต้องการหาเส้นขอบฟ้า มีค่าตั้งแต่ 1 ถึง 3,000
2. บรรทัดต่อไปแต่ละบรรทัดเป็นข้อมูลของอาคารแต่ละหลังในรูปแบบ Li Hi Ri โดยแต่ละตัวมีค่าตั้งแต่ 1 ถึง 255
3. ระหว่างข้อมูลแต่ละตัวในข้อ ๒. คั่นด้วยเว้นวรรค 1 วรรค
ข้อมูลส่งออก
1. ผลลัพธ์ของโปรแกรมมีเพียงบรรทัดเดียว ได้แก่ เส้นขอบฟ้าที่เกิดจากข้อมูลของอาคารที่เป็นข้อมูลนำเข้า โดยเส้นขอบฟ้ามีรูปแบบดังนี้ v1 v2 v3 … vn-2 vn-1 vn เมื่อ i เป็นจำนวนคี่ vi จะแทนตำแหน่งของเส้นขอบฟ้าตามแกนนอน และ เมื่อ i เป็นจำนวนคู่ v i แทนความสูงของเส้นขอบฟ้าที่ตำแหน่งนั้น ด้วยเหตุนี้ vn จึงมีค่าเป็น 0 เนื่องจากเส้นขอบฟ้าลดลงสู่ระดับพื้น
2. ผลลัพธ์แต่ละจำนวนให้คั่นด้วยเว้นวรรค 1 วรรค
ที่มา: การแข่งขันคอมพิวเตอร์โอลิมปิก สอวน. ครั้งที่ 2 มหาวิทยาลัยบูรพา
| ตัวอย่างข้อมูลนำเข้า | ตัวอย่างข้อมูลส่งออก |
| 2 1 11 5 2 6 7 | 1 11 5 6 7 0 |
| 8 1 11 5 2 6 7 12 7 16 14 3 25 19 18 22 3 13 9 23 13 29 24 4 28 | 1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0 |
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้
กำลังออนไลน์: 20 ผู้เยี่ยมชมและ 0 สมาชิก (0 บอท)