COCI 2014/2015 contest4- 최대치 최소치 > 문제은행 : 정보올림피아드&알고리즘




2904 : 최대치 최소치

제한시간
1000 ms   
메모리제한
128 MB   
해결횟수
29 회   
시도횟수
258 회   

문제

형제 사이인 최대치(이하 대치)와 최소치(이하 소치)가 게임을 한다.
N개의 정수가 주어지고 소치부터 게임을 시작한다.


* 소치가 N개의 정수 중에서 최소값을 찾고 그 다음 최소값으로 교환한다.
* 대치가 N개의 정수 중에서 최대값을 찾고 그 다음 최대값으로 교환한다.
* N개의 정수 중에 서로 다른 종류의 수가 2가지 이하라면 현재 차례의 사람은 게임에서 패하게 되며 게임이 종료된다.


예를 들어 4개의 수 3 1 2 1 이 주어졌다고 하자.
먼저 소치가 최소값 1을 찾아 다음 최소값인 2로 바꾸면 3 2 2 1이 된다.
다음 대치가 최대값 3을 찾고 다음 최대값인 2로 바꾸면 2 2 2 1이 된다.
서로 다른 종류의 수가 2가지 이하이므로 대치가 승리하였고 남은 수들 중 최소값은 1, 최대값은 2이다.


N개의 수들이 주어질 때, 게임의 승자와 현재 남은 수들 중 최소값과 최대값을 출력하는 프로그램을 작성하시오.


입력형식

첫 행에 수의 개수 N (1 ≤ N ≤ 100,000) 이 주어진다.
다음 행에 N개의 정수 Ai ( 1 ≤ Ai ≤ 100,000)가 공백으로 구분되어 주어진다.


출력형식

첫 행에 게임의 승자를 출력한다.
대치가 이긴 경우 MAX를 소치가 이긴 경우 MIN을 출력한다.
두 번째 행에 현재 남은 수들 중 최소값과 최대값을 공백으로 구분하여 출력한다.


입력 예

3
3 3 3

출력 예

MAX
3 3

입력 예

4
3 1 2 1

출력 예

MAX
1 2

입력 예

7
2 1 3 3 5 4 1

출력 예

MAX
2 3


경기도 안양시 동안구 평촌대로 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