อนุภาคแบบสั่งทำพิเศษจำนวน N อนุภาควางเรียงกัน เราจะเรียกอนุภาคดังกล่าวว่าอนุภาคที่ 1, 2, ..., ถึง อนุภาคที่ N ตามลำดับ อนุภาคแต่ละอนุภาคจะมีค่าพลังงานสะสมอยู่ กล่าวคืออนุภาคที่ i จะมีพลังงานสะสมเท่ากับ Xi หน่วย

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

                หัวหน้าห้องปฏิบัติการวานให้คุณทดลองนำาอนุภาคทั้ง N อันมาชนกัน โดยหัวหน้าได้ระบุคำสั่งไว้ดังนี้ 1. ให้เลือกอนุภาคสองอนุภาคที่ติดกัน ที่ชนกันแล้วสลายตัวให้พลังงานมากที่สุด ถ้ามีหลายทางเลือกให้เลือกคู่ของอนุภาคที่ประกอบด้วยอนุภาคที่มีหมายเลขน้อยที่สุด 2. นำาอนุภาคทั้ง สองมาชนกัน ทำไปเรื่อยๆ จนกระทั่งอนุภาคหมด หรือเหลือแค่ 1 อนุภาค (ไม่สามารถชนกับใครได้อีก)

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

                ตัวอย่างการดำาเนินการเป็นดังนี้ สมมติมีอนุภาค 7 อนุภาคที่มีพลังงานสะสมดังนี้

1 2 4 3 1 2 3

                คุณเลือกชนอนุภาคที่ 2 กับ 3 (สังเกตว่า คู่ของอนุภาค 3 กับ 1 ก็มีผลต่างเท่ากับ 2 เหมือนกัน แต่เราไม่เลือกเนื่องจากอนุภาคที่ 2 มีหมายเลขน้อยกว่า) ได้พลังงาน 2 หน่วย

                หลังจากนั้น เราจะเหลืออนุภาค 5 อนุภาค

1 3 1 2 3

                เลือกคู่อนุภาค 1 กับอนุภาค 4 ได้พลังงาน 2 หน่วย

1 2 3

                เลือกคู่อนุภาค 5 กับอนุภาค 6 ได้พลังงาน 1 หน่วย

3

                เมื่อเหลืออนุภาคเดียวเราจะไม่สามารถชนได้อีก รวมแล้วได้พลังงานทั้งหมด 5 หน่วย

งานของคุณ

รับข้อมูลพลังงานสะสมของอนุภาค จากนั้นคำนวณพลังงานทั้งหมดที่ได้รับจากการชนอนุภาคด้วยวิธีการตามที่หัวหน้าห้องปฏิบัติการระบุ

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

บรรทัดแรก ระบุจำนวนเต็ม N (1 ≤ N ≤ 1,000) แทนจำนวนอนุภาค
อีก N บรรทัด ระบุพลังงานสะสมของแต่ละอนุภาค กล่าวคือ บรรทัดที่ 1 + i จะระบุจำนวนเต็ม Xi (1 ≤ Xi ≤ 1,000,000) แทนพลังงานสะสมของอนุภาคที่ i

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

มีบรรทัดเดียว คือพลังงานรวมทั้งหมดที่ได้รับ

ทีมา: การแข่งขัน YTOPC กุมภาพันธ์ 2552