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

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

Citystar

면접 대비

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

요약
각 거리에서 다섯 집 번호의 범위(최댓값에서 최솟값을 빼고 1을 더한 값)가 가장 작은 조합을 찾고, 범위가 같으면 더 작은 번호 쪽을 고른다.
난이도

보통10점 중 6점

유형
정렬, 슬라이딩 윈도우, 투 포인터, 배열
정답자
아직 제출이 없습니다

문제

별의 도시 Citystar 행성의 도시들은 별 모양을 하고 있다. 가운데에 작고 둥근 도시 중심부가 있고, 그곳에서 여러 개의 곧은 도로가 바깥쪽으로 뻗어 나간다. 같은 도로에 사는 사람들은 서로 유대감을 느끼고, 서로 다른 도로 사이에는 가벼운 경쟁 의식이 있다. 이 행성에서는 프로그래밍 대회가 열리는데, 각 도로는 하나의 팀으로 참가한다. 주최 측은 각 도로에 좋은 팀 구성원을 추천해 주고 싶어 하며, 공정성을 위해 외계인인 당신에게 도움을 요청했다.

각 도로에는 한쪽 편에만 집이 있으며, 도시 중심부에서부터 1,2,3,…1, 2, 3, \dots 순서로 번호가 매겨져 있다. 모든 집의 크기는 같고, 한 집에는 최대 한 명의 프로그래머만 산다(둘이 함께 살 수는 없다). 각 도로에 대해 그 도로에 사는 프로그래머들의 집 번호가 주어진다.

팀은 구성원들이 서로 가까이 살수록 더 자주 모여 연습할 수 있다. 따라서 다섯 명의 프로그래머(정규 구성원 3명, 후보 1명, 코치 1명)를 포함하면서 집 번호의 범위가 가장 작은 팀을 찾아야 한다. 여기서 범위란 (가장 큰 집 번호) −- (가장 작은 집 번호) +1+ 1 로 정의한다. 예를 들어 집 번호 65,71,64,61,8165, 71, 64, 61, 81 을 고르면 범위는 81−61+1=2181 - 61 + 1 = 21 이 된다.

범위가 가장 작은 팀이 여러 개라면, 대회가 열리는 도시 중심부에 가장 가까운(즉 집 번호가 더 작은) 팀을 선택한다.

입력

첫째 줄에는 시나리오의 수가 주어진다. 각 시나리오는 하나의 도로를 나타내며 한 줄에 주어진다. 줄의 첫 번째 수는 그 도로에 사는 프로그래머의 수 kk (5≤k≤100 0005 \le k \le 100\,000)이고, 그 뒤로 각 프로그래머의 집 번호가 하나씩 주어진다(집 번호는 11 이상 10 000 00010\,000\,000 이하이며 한 도로 안에서 서로 다르다).

출력

각 시나리오에 대해 먼저 Scenario #i: 형식의 줄을 출력한다. 여기서 ii 는 11 부터 시작하는 시나리오 번호이다. 그다음 줄에 선택한 팀을 다음 형식으로 출력한다. 먼저 범위를 출력하고, 이어서 선택한 다섯 개의 집 번호를 오름차순으로, 각 번호 앞에 공백을 하나씩 두고 출력한다. 연속한 두 시나리오의 출력 사이는 빈 줄 하나로 구분한다.

예제1

  1. 예제 1

    입력
    2
    10 65 2 71 123 7 45 64 4 61 81
    16 111 103 117 105 102 113 119 107 11 3 17 5 2 13 19 7
    
    예상 출력
    Scenario #1:
    21: 61 64 65 71 81
    
    Scenario #2:
    10: 2 3 5 7 11