아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

크리스마스 밀

시간 제한1초메모리 제한32 MB

요약
최소 높이 짚단 하나를 다음 높이로 올리는 차례와 최대 높이를 낮추는 차례를 서로 다른 높이가 두 개 남을 때까지 반복한 뒤 승자와 양 끝 높이를 구합니다.
난이도

보통10점 중 6점

유형
정렬, 누적 합, 그리디, 게임 이론
정답자
아직 제출이 없습니다

문제

미르코와 슬라브코는 매년 성 루치아 축일에 크리스마스 밀을 심는다. 밀 줄기는 자라는 속도가 서로 달라서 시간이 지나면 밀밭이 꽤 지저분해진다. 두 사람은 다음 게임을 해서 이 문제를 해결하기로 했다.

  • 미르코의 차례에는 높이가 가장 낮은 줄기 하나를 골라, 그 줄기보다 높은 줄기 중 가장 낮은 줄기와 같은 높이가 되도록 늘린다.
  • 슬라브코의 차례에는 높이가 가장 높은 줄기 하나를 골라, 그 줄기보다 낮은 줄기 중 가장 높은 줄기와 같은 높이가 되도록 자른다.
  • 서로 다른 높이가 세 종류 이상 남아 있는 동안 게임이 이어지고, 자기 차례에 수를 둘 수 없는 사람이 진다.

미르코가 먼저 시작한다. 모든 줄기의 높이가 주어질 때 게임의 승자와, 게임이 끝난 시점의 가장 낮은 줄기의 높이와 가장 높은 줄기의 높이를 구한다.

입력

첫째 줄에 밀 줄기의 개수 NN이 주어진다. (1≤N≤1051 \le N \le 10^5)

둘째 줄에 각 줄기의 높이를 나타내는 NN개의 정수가 공백으로 구분되어 주어진다. 높이는 모두 10510^5 이하의 양의 정수다.

출력

첫째 줄에 미르코가 이기면 Mirko, 슬라브코가 이기면 Slavko를 출력한다.

둘째 줄에 게임이 끝난 시점의 가장 낮은 줄기의 높이와 가장 높은 줄기의 높이를 공백으로 구분해 출력한다.

힌트

첫 번째 예제에서는 모든 줄기의 높이가 같아 서로 다른 높이가 세 종류에 못 미치므로 미르코가 첫 수를 둘 수 없다. 따라서 슬라브코가 이긴다.

예제3

  1. 예제 1

    입력
    3
    3 3 3
    
    예상 출력
    Slavko
    3 3
    
  2. 예제 2

    입력
    4
    3 1 2 1
    
    예상 출력
    Slavko
    1 2
    
  3. 예제 3

    입력
    7
    2 1 3 3 5 4 1
    
    예상 출력
    Slavko
    2 3