Pairsumonious Numbers

면접 대비

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

요약
N개 수의 모든 쌍별 합이 주어질 때, 원래 수 N개를 오름차순으로 복원하고, 가능한 답이 여러 개면 사전순으로 가장 앞선 것을 출력하거나 불가능을 보고한다.
난이도

보통10점 중 6점

유형
정렬, 수학, 완전 탐색, 구현
정답자
아직 제출이 없습니다

문제

2<N<102 < N < 10을 만족하는 NN개의 정수가 있습니다. 이 수들 중 서로 다른 두 개를 골라 더하는 모든 경우를 생각하면 N(N−1)/2N(N-1)/2개의 합을 얻습니다. 이 N(N−1)/2N(N-1)/2개의 쌍별 합이 주어질 때, 원래의 NN개의 정수를 복원하세요.

입력

입력은 여러 줄로 이루어집니다. 각 줄은 먼저 정수 NN을 담고, 이어서 공백으로 구분된 N(N−1)/2N(N-1)/2개의 정수(쌍별 합)가 주어집니다. 각 줄을 독립적인 하나의 질의로 처리하며, 파일의 끝까지 모든 줄을 읽습니다.

출력

각 줄마다, 쌍별 합이 주어진 수들과 정확히 일치하는 NN개의 정수를 비내림차순으로 한 줄에 출력하세요. 조건을 만족하는 정수 집합이 여러 개라면, 그중 사전순으로 가장 작은 수열을 출력하세요. (각 후보는 이미 비내림차순으로 정렬되어 있으며, 두 수열은 앞에서부터 원소 단위로 비교합니다.) 조건을 만족하는 집합이 없으면 Impossible을 출력하세요.

예제1

  1. 예제 1

    입력
    3 1269 1160 1663
    3 1 1 1
    5 226 223 225 224 227 229 228 226 225 227
    5 216 210 204 212 220 214 222 208 216 210
    5 -1 0 -1 -2 1 0 -1 1 0 -1
    5 79950 79936 79942 79962 79954 79972 79960 79968 79924 79932
    
    예상 출력
    383 777 886
    Impossible
    111 112 113 114 115
    101 103 107 109 113
    -1 -1 0 0 1
    39953 39971 39979 39983 39989