โจทย์ programming ที่แสนเข้ากับสถานการณ์ ณ เวลานี้

Programming Democracy

ประเทศหนึ่งในแถบเอเชียตะวันออกเฉียงใต้ มีการปกครองในรูปแบบรัฐสภา โดย ส.ส. ในสภาจะเป็นผู้ลงคะแนนเลือกนายกรัฐมนตรี ซึ่งผู้ที่จะได้รับเลือกเป็นนายกรัฐมนตรีนั้นจะต้องได้รับเสียงสนับสนุนจาก ส.ส. มากกว่าครึ่งหนึ่งของจานวน ส.ส. ทั้งหมดในสภา จากนั้นนายกรัฐมนตรีก็จะเป็นผู้จัดตั้งคณะรัฐมนตรีขึ้นมาทำหน้าที่บริหารประเทศต่อไป

ส.ส. แต่ละคนนั้นก็จะสังกัดพรรคการเมืองต่างๆ หากมีพรรคการเมืองใดที่มี ส.ส. มากกว่าครึ่งหนึ่งของจำนวน ส.ส. ทั้งหมดในสภา พรรคการเมืองนั้นก็จะเป็นผู้ครองเสียงข้างมากในสภา และจะสามารถจัดตั้งรัฐบาลพรรคเดียวขึ้นมาได้ แต่หากไม่มีพรรคการเมืองใดที่มีจานวน ส.ส. เกินครึ่ง ก็จะต้องมีการจับขั้วกันระหว่างพรรคการเมืองบางพรรค เพื่อให้จำนวน ส.ส. ของพรรคการเมืองเหล่านั้นรวมกันแล้วมากกว่าครึ่งหนึ่งของจานวน ส.ส. ทั้งหมด ก็จะสามารถครองเสียงข้างมากในสภา และจัดตั้งรัฐบาลผสมขึ้นมาได้

ในการเลือกตั้ง ส.ส. ครั้งล่าสุด ผลปรากฏว่าไม่มีพรรคการเมืองใดที่มีจำนวน ส.ส. เกินครึ่ง ดังนั้น พรรคการเมืองแต่ละพรรคต่างก็พยายามที่จะไปจับขั้วกับพรรคการเมืองอื่น เพื่อจัดตั้งรัฐบาลผสมขึ้นมาให้ได้ หัวหน้าพรรคการเมืองแต่ละพรรคก็อยากจะทราบว่า พรรคการเมืองของตนจะต้องไปจับขั้วกับพรรคการเมืองอื่นอย่างน้อยกี่พรรค จึงจะทำให้จานวน ส.ส. ทั้งหมดของพรรคการเมืองของตนและของทุกพรรคที่ไปจับขั้วด้วย รวมกันแล้วมากกว่าครึ่งหนึ่งของจานวน ส.ส. ทั้งหมดในสภา

นักศึกษาจงเขียนโปรแกรมเพื่อคานวณว่าพรรคการเมืองที่ได้คะแนนมากที่สุดจะต้องจับขั้วกับพรรคการเมืองอีกกี่พรรคจึงจะจัดตั้งรัฐบาลได้
กำหนดให้อินพุตอยู่ในรูปแบบ N_Party N1 N2 …. โดยที่ N_Party คือจานวนพรรค(ไม่เกิน 50 พรรค) และ N1 N2 … คือ จำนวน สส ในแต่ละพรรค (โดยอาจจะไม่เรียงลาดับจำนวนได้)

ตัวอย่าง (ตัวหนาคืออินพุต ตัวเอียงคือเอาท์พุต)

4
20
100
90
1
Require 1 Party

5
21
20
20
20
19
Require 2 Parties

 

เครดิตโจทย์ : อาจารย์ที่คณะ 555555

เครดิตภาพ : http://www.panoramio.com/photo/75991804

Leave a Reply

Your email address will not be published. Required fields are marked *