USACO 2008 January Bronze- 선거(소들의 선거) > 문제은행 : 정보올림피아드&알고리즘




1376 : 선거(소들의 선거)

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
24 회   
시도횟수
44 회   

문제

포악한 주인이었던 농부 창호를 내쫓은 소들이 자신들의 우두머리를 뽑기 위해서 처음으로 선거를 하고자 한다. 평소에 창호네 농장에 관심이 많았고, 이참에 창호의 농장을 차지하고자 결심한 정택이는 N(1≤N≤50,000)마리의 소가 참가하는 선거에서 우두머리가 될 가능성이 높은 소가 누구인지 알아낸 다음에, 사전 접촉을 하여서 농장 합병을 한걸음 더 수월하게 이루고자 한다.

 

선거는 2번의 투표로 이루어진다. 첫 번째 투표에는 K(1≤K≤N) 마리의 득표수가 높은 소들을 제외한 나머지 소들을 탈락 시키고, 두 번째 투표 에서는 탈락 되지 않은 K마리의 소 중에 가장 높은 득표를 한 소가 우두머리로 선출된다.

 

선거 방식을 알게 된 정택이는, 창호 농장의 모든 소들에게 설문 조사를 하여 모든 소에 대해서 첫 번째 선거에 몇 표를 얻을지, 두 번째 까지 탈락을 하지 않았을 경우에 몇표를 얻을지를 조사 하게 되었고 이를 토대로 어떤 소가 당선 확률이 가장 높은지 알고자 한다. 조사된 예상 득표수에는 해당 회수에 같은 득표수를 얻는 소들은 존재 하지 않는다고 한다.

 

정택이가 조사한 데이터를 토대로 어떤 소의 당첨 확률이 가장 높은지 알아보는 프로그램을 작성해보자.


입력형식

첫 번째 줄에는 소들의 마리수 N과 첫 번째에 뽑히게 되는 소들의 마리수 K가 입력된다. 2번째 줄부터 N+1번째 줄에는 기호 1번부터 N번까지의 소들의 첫 번째 투표 때의 예상 득표수와, 두 번째 투표때의 예상 득표수가 입력이 되며, 이는 1이상 1,000,000,000이하의 숫자이다.


출력형식

입력된 예상 득표수를 가지고 선거를 치룰 때 당선이 되는 소의 번호를 출력한다.


입력 예

5 3 
3 10 
9 2 
5 6 
8 4 
6 5

출력 예

5


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP