N의 배수 (2)

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

요약
2N-1개의 수에서 합이 N으로 나누어떨어지는 N개를 골라 출력하고, 불가능하면 -1을 출력합니다.
난이도

보통10점 중 7점

유형
누적 합, 조합론, 수학
정답자
아직 제출이 없습니다

문제

2N−12N-1개의 수가 주어진다. 이 중 합이 NN으로 나누어 떨어지는 수 NN개를 구하여라.

입력

첫째 줄에 NN이 주어진다. (1≤N≤5 0001 \le N \le 5\ 000)

둘째 줄에 00이상 NN미만의 수 2N−12N-1개가 공백으로 구분되어 주어진다.

출력

첫째 줄에, 조건을 만족하는 수 NN개를 공백으로 구분하여 출력한다.

답을 만족하는 경우가 여럿 있는 경우, 그 중 임의의 하나를 출력하면 정답으로 인정된다. 출력하는 수들의 순서는 관계 없다.

답을 만족하는 수들이 존재하지 않는 경우 -1을 출력하여라.

예제1

  1. 예제 1

    입력
    4
    1 2 3 0 1 2 3
    
    예상 출력
    1 1 3 3