1080 : สามเหลี่ยมอีกครั้ง (triagain)
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 16 megabyte(s)
      บรรยากาศรอบตัวเย็นขึ้นอย่างน่าประหลาด ทันใดนั้น แม่ครัวก็ได้เตือนคุณว่า คุณลืมเตรียมท่อนไม้มาจุดไฟเตาผิงนั่นเอง ลูกน้องแต่ละคนต่างเคร่งเครียดอยู่กับหน้าที่ที่ได้รับ ดูเหมือนว่าคุณจะต้องลงมือออกไปเก็บท่อนไม้ด้วยตัวเองแล้ว   

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

      “เทพเจ้า ตัวเลขทรงโปรดรูปสามเหลี่ยมมาก ท่านต้องการอนุโมทนาบุญด้วยการมอบท่อนไม้ที่มีอยู่ให้กับคนที่จำเป็นต้องใช้มัน แต่ท่านเทพจะทรงพระกริ้วถึงขีดสุดเมื่อพบว่า ในจำนวนทั้งหมดของท่อนไม้ที่หยิบไปนั้น มีท่อนไม้สามท่อนที่ไม่สามารถต่อกันเป็นรูปสามเหลี่ยมได้ ระวังอย่าให้ท่านเทพโกรธนะจ๊ะ ^ - ^””

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

      เราจะกล่าวว่าเซตของท่อนไม้ทั้งหมดที่คุณหยิบไปเป็นเซตสามเหลี่ยม ก็ต่อเมื่อ ถ้ามีท่อนไม้สามท่อนใด ๆ ในเซต ต้องสามารถนำไปประกอบเป็นด้านของรูปสามเหลี่ยมที่มีพื้นที่มากกว่าศูนย์ได้เสมอ  เช่น {4,4,5,7} ถือว่าเป็นเซตสามเหลี่ยม ส่วน {3,5,5,9} ไม่ถือว่าเป็นเซตสามเหลี่ยม เป็นต้น

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

งานของคุณ

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

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


      บรรทัดแรก มีจำนวนเต็มบวก N (1≤N≤30,000) ซึ่งระบุจำนวนท่อนไม้ทั้งหมด
 อีก N บรรทัดถัดไป แต่ละบรรทัดมีจำนวนเต็มบวกหนึ่งตัว ระบุความยาวของท่อนไม้แต่ละท่อน ซึ่งทุกท่อนมีความยาวเป็นจำนวนเต็มที่อยู่ในช่วง [1,500]

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

      มีจำนวนเต็มหนึ่งจำนวน ระบุจำนวนท่อนไม้มากที่สุดในเซตสามเหลี่ยมที่เป็นไปได้

โจทย์โดย: ศิระ ทรงพลโรจนกุล
ที่มา: TOI.C:02-2009

ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
10
7
1
2
8
10
6
1
7
9
9
7

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

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