Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 32 megabyte(s)
ประเทศหนึ่งในแถบเอเชียตะวันออกเฉียงใต้ มีการปกครองในรูปแบบรัฐสภา โดย ส.ส. ในสภาจะเป็นผู้ลงคะแนนเลือกนายกรัฐมนตรี ซึ่งผู้ที่จะได้รับเลือกเป็นนายกรัฐมนตรีนั้นจะต้องได้รับเสียงสนับสนุนจาก ส.ส. มากกว่าครึ่งหนึ่งของจำนวน ส.ส. ทั้งหมดในสภา จากนั้นนายกรัฐมนตรีก็จะเป็นผู้จัดตั้งคณะรัฐมนตรีขึ้นมาทำหน้าที่บริหารประเทศต่อไป
ส.ส. แต่ละคนนั้นก็จะสังกัดพรรคการเมืองต่างๆ หากมีพรรคการเมืองใดที่มี ส.ส. มากกว่าครึ่งหนึ่งของจำนวน ส.ส. ทั้งหมดในสภา พรรคการเมืองนั้นก็จะเป็นผู้ครองเสียงข้างมากในสภา และจะสามารถจัดตั้งรัฐบาลพรรคเดียวขึ้นมาได้ แต่หากไม่มีพรรคการเมืองใดที่มีจำนวน ส.ส. เกินครึ่ง ก็จะต้องมีการจับขั้วกันระหว่างพรรคการเมืองบางพรรค เพื่อให้จำนวน ส.ส. ของพรรคการเมืองเหล่านั้นรวมกันแล้วมากกว่าครึ่งหนึ่งของจำนวน ส.ส. ทั้งหมด ก็จะสามารถครองเสียงข้างมากในสภา และจัดตั้งรัฐบาลผสมขึ้นมาได้
ในการเลือกตั้ง ส.ส. ครั้งล่าสุด ผลปรากฏว่าไม่มีพรรคการเมืองใดที่มีจำนวน ส.ส. เกินครึ่ง ดังนั้น พรรคการเมืองแต่ละพรรคต่างก็พยายามที่จะไปจับขั้วกับพรรคการเมืองอื่น เพื่อจัดตั้งรัฐบาลผสมขึ้นมาให้ได้ หัวหน้าพรรคการเมืองแต่ละพรรคก็อยากจะทราบว่า พรรคการเมืองของตนจะต้องไปจับขั้วกับพรรคการเมืองอื่นอย่างน้อยกี่พรรค จึงจะทำให้จำนวน ส.ส. ทั้งหมดของพรรคการเมืองของตนและของทุกพรรคที่ไปจับขั้วด้วย รวมกันแล้วมากกว่าครึ่งหนึ่งของจำนวน ส.ส. ทั้งหมดในสภา
งานของคุณ
จงเขียนโปรแกรมเพื่อรับจำนวน ส.ส. ของพรรคการเมืองต่างๆ และคำนวณว่าพรรคการเมืองแต่ละพรรคจะต้องไปจับขั้วกับพรรคการเมืองอื่นอย่างน้อยกี่พรรค จึงจะสามารถครองเสียงข้างมากในสภาได้
ข้อมูลนำเข้า
บรรทัดแรกระบุจำนวนเต็ม N (3 ≤ N ≤ 300,000) แทนจำนวนพรรคการเมืองทั้งหมด
อีก N บรรทัดต่อมา ในบรรทัดที่ i+1 (1 ≤ i ≤ N) จะระบุจำนวนเต็ม Mi (1 ≤ Mi ≤ 1,000,000) แทนจำนวน ส.ส. ของพรรคการเมืองที่ i
รับประกันว่าจะไม่มีพรรคการเมืองใดที่มีจำนวน ส.ส. มากกว่าครึ่งหนึ่งของจำนวน ส.ส. ทั้งหมดในสภา และจำนวน ส.ส. ทั้งหมดจะมีไม่เกิน 2,000,000,000 คน
ข้อมูลส่งออก
มีทั้งหมด N บรรทัด โดยในบรรทัดที่ i (1 ≤ i ≤ N) แสดงจำนวนพรรคการเมืองน้อยที่สุดที่พรรคการเมืองที่ i ต้องไปจับขั้วด้วยเพื่อให้สามารถครองเสียงข้างมากในสภา
การให้คะแนน
30% ของข้อมูลทดสอบ จะมี N ≤ 5,000
ที่มา
การแข่งขัน IOI Thailand League เดือนมิถุนายน 2553
โจทย์โดย: สุธี เรืองวิเศษ
| ตัวอย่างข้อมูลนำเข้า | ตัวอย่างข้อมูลส่งออก |
| 5 7 1 1 2 3 | 1 1 1 1 1 |
| 7 5 5 6 7 5 5 8 | 3 3 2 2 3 3 2 |
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้