1024 : Factory
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 64 megabyte(s)
นายใหญ่และนายหญิงมีธุรกิจขนาดยักษ์ โดยธุรกิจเหล่านี้มีสายการผลิตเป็นลำดับที่แน่นอน การผลิตเริ่มจากโรงงานที่หนึ่งไปยังโรงงานที่ n โดยโรงงานแต่ละแห่งนั้นมีกำไรไม่เท่ากัน เนื่องจากนายใหญ่และนายหญิงต้องการแบ่งหน้าที่การควบคุมดูแลโรงงานออกให้ลูกสามคนโดยการแบ่งงานนั้นต้องการให้ลูกแต่ละคนได้กำไรเท่าเทียมกันที่สุด โดยความเท่าเทียมในที่นี้วัดจากผลต่างของกำไรของลูกคนที่ได้กำไรสูงสุดกับของลูกคนที่ได้กำไรต่ำสุด การแบ่งจะถือว่าเท่าเทียมมากที่สุดถ้าค่าผลต่างดังกล่าวมีค่าน้อยที่สุด และลูกแต่ละคนจะต้องได้รับงานที่ต่อเนื่องกันเท่านั้น และจะไม่มีโรงงานไหนที่ไม่ได้รับการดูแล

ยกตัวอย่างในกรณีที่ n=6 การแบ่ง {1,2} {3,4,5} และ {6} ถือเป็นการแบ่งที่ถูกต้อง แต่การแบ่ง {1,3} {2} {4,5,6} ถือเป็นการแบ่งที่ผิด เพราะว่าสายการผลิตของโรงงานของลูกคนแรกไม่ต่อเนื่องกัน

โจทย์
จงเขียนโปรแกรมเพื่อหาวิธีแบ่งโรงงานของนายใหญ่และนายหญิงให้แก่ลูกทั้งสาม

ข้อมูลนำเข้า
ข้อมูลนำเข้าเป็นกำไรของแต่ละโรงงานตามลำดับ โดยบรรทัดแรกเก็บจำนวนเต็ม n ซึ่งเป็นจำนวนของโรงงานทั้งหมด จากนั้น n บรรทัด (1 < n < 1000) โดยบรรทัดที่ i จะมีจำนวนเต็มของกำไรของโรงงานที่ i+1 ซึ่งกำไรของแต่ละโรงงานจะอยู่ในช่วง [-1000,1000]

ข้อมูลส่งออก
ข้อมูลส่งออกประกอบด้วยจำนวนเต็มสองตัวเว้นด้วยช่องว่างหนึ่งช่อง โดยตัวแรกคือหมายเลขโรงงานของลูกคนที่สอง และตัวที่สองคือหมายเลขโรงงานของลูกคนที่สาม

ที่มา: การแข่งขันคณิตศาสตร์ วิทยาศาสตร์ โอลิมปิกแห่งประเทศไทย สาขาวิชาคอมพิวเตอร์ ประจำปี 2548
ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
5
3 2 5 -1 6		 3 4

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

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