โจทย์เขียนโปรแกรม: majority

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา

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

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

ข้อมูลเข้า

อยู่ในไฟล์ชื่อ input.txt

บรรทัดแรกมีจำนวนเต็ม n (1 <= n <= 16,000,000) และ m (1 <= m <= 16,000,000) แสดงจำนวนประชาชนที่ลงคะแนนเสียงเลือกตั้งและจำนวนผู้สมัครรับเลือกตั้ง ตามลำดับ

อีก n บรรทัดต่อไปมีจำนวนเต็ม v (1 <= v <= m) บรรทัดละตัว หมายความว่าประชาชนคนหนึ่งลงคะแนนเสียงให้ผู้สมัครหมายเลข v

ข้อมูลออก

ถ้าหากไม่มีผู้สมัครคนใดได้รับคะแนนเสียงเกินครึ่งหนึ่ง ให้พิมพ์ NO ออกทาง standard output ในบรรทัดแรก

มิเช่นนั้น ให้พิมพ์หมายเลขของผู้สมัครที่ได้รับคะแนนเสียงเกินครึ่งออกทาง standard output ในบรรทัดแรกเช่นกัน

ตัวอย่าง

ข้อมูลเข้า 1

4 3
1
2
3
1

ข้อมูลออก 1

NO

ข้อมูลเข้า 2

10 3
1
1
3
1
1
1
2
2
1
3

ข้อมูลออก 2

1

ข้อกำหนด

โปรแกรมของคุณจะต้องทำงานเสร็จสิ้นภายในเวลา 7 วินาที (Please wait up to 15 minutes for grader) และใช้หน่วยความจำไม่เกิน 1 MB