COCI 2012/2013 contest4 1- 과자 가져가기(OREHNJACA) > 문제은행 : 정보올림피아드&알고리즘




1623 : 과자 가져가기(OREHNJACA)

제한시간
1000 ms   
메모리제한
32 MB   
해결횟수
2 회   
시도횟수
5 회   

문제

1 × L 격자의 각 칸에 과자가 하나씩 있다. 

N명의 학생들은 각자 P번째에서부터 K번째 칸까지 위치한 과자를 가져갈 것이다.

각 학생이 가져갈 과자의 수는 정확히 K-P+1라고 예상할 수 있다. 

하지만 실제로는 학생들이 과자를 순서대로 가져가기 때문에 마지막에 과자를 가져가는 사람이 불리하다.

P와 K가 주어질 때, 가장 과자를 많이 가져갈 것으로 예측되는 학생의 번호와, 

실제로 가장 과자를 많이 가져가는 학생의 번호를 구하는 프로그램을 작성하여라.


입력형식

첫 번째 줄에 L이 주어지고 두 번째 줄에 N이 주어진다. (1 ≤ L, N ≤ 1,000)
세 번째 줄부터 N개의 줄에는 각 학생의 P, K 값이 주어진다. (1 ≤ P ≤ K ≤ L)
먼저 입력된 학생이 과자를 먼저 가져간다.


출력형식

첫 번째 줄에는 가장 과자를 많이 가져갈 것으로 예측되는 학생의 번호를 출력하고, 두 번째 줄에는 실제로 가장 과자를 많이 가져가는 학생의 번호를 출력한다. 그런 학생이 여러 명이면 가장 작은 번호를 출력한다.


입력 예

10 
3 
2 4 
7 8 
6 9

출력 예

3
1

입력 예

10
3
1 3
5 7
8 9

출력 예

1
1

입력 예

10
5
1 1
1 2
1 3
1 4
7 8

출력 예

4
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