1137 : แม่น้ำ (river)
Problem type : Batch
Time limit : 0.5 second(s)
Memory limit : 32 megabyte(s)
คุณและผองเพื่อนรวมทั้งหมด N คน ได้ออกเดินทางผจญภัยไปรอบโลก ระหว่างทางได้พบกับแม่น้ำสายหนึ่ง ที่จะต้องพายเรือข้ามไป คุณมีเรือเพียงลำเดียว ซึ่งสามารถจุคนได้เพียง 2 คนเท่านั้น นอกจากนี้ แต่ละคนก็จะมีความเร็วในการพายเรือที่แตกต่างกัน และหากมีคน 2 คนอยู่ในเรือ ความเร็วในการพายเรือจะเท่ากับความเร็วของคนที่พายช้ากว่าเสมอ

ตัวอย่างเช่น หากมีคนทั้งหมด 4 คน คือ A, B, C และ D ซึ่งใช้เวลาในการพายเรือข้ามแม่น้ำ 2, 4, 5 และ 8 นาที ตามลำดับ จะมีวิธีที่สามารถทำให้ทุกคนข้ามแม่น้ำได้ เช่น
  • A และ B พายเรือข้ามไป ใช้เวลา 4 นาที
  • A พายเรือกลับมา ใช้เวลา 2 นาที
  • A และ C พายเรือข้ามไป ใช้เวลา 5 นาที
  • A พายเรือกลับมา ใช้เวลา 2 นาที
  • A และ D พายเรือข้ามไป ใช้เวลา 8 นาที
รวมใช้เวลาทั้งหมด 21 นาที ซึ่งวิธีนี้เป็นวิธีที่ใช้เวลาน้อยที่สุดแล้ว

คุณต้องการหาว่า จะต้องใช้เวลาอย่างน้อยกี่นาที จึงจะทำให้ทุกคนสามารถข้ามแม่น้ำไปได้

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

ข้อมูลนำเข้า
บรรทัดแรกระบุจำนวนเต็ม N (1 ≤ N ≤ 1,000,000) แทนจำนวนคนทั้งหมด

บรรทัดต่อมาระบุจำนวนเต็มบวก N ตัว แทนเวลาที่แต่ละคนใช้ในการพายเรือข้ามแม่น้ำ เรียงจากน้อยไปหามาก โดยตัวเลขแต่ละตัวจะมีค่าไม่เกิน 1,000,000,000 และอาจซ้ำกันได้

ข้อมูลส่งออก
มีบรรทัดเดียว แทนเวลาที่น้อยที่สุดที่ทำให้ทุกคนสามารถข้ามแม่น้ำไปได้

การให้คะแนน
20% ของข้อมูลทดสอบ จะมี N ≤ 10
40% ของข้อมูลทดสอบ จะมี N ≤ 1,000
60% ของข้อมูลทดสอบ จะมี N ≤ 100,000

ที่มา
โจทย์โดย: สุธี เรืองวิเศษ

ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
4
2 4 5 8		 21
5
1 3 5 5 10		 26

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

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