같은 합 timer 5s memory 1024MB

서로 다른 정수들의 집합이 주어진다. 당신은 이들을 두 개의 비어 있지 않은 부분집합으로 나누어, 각 원소가 정확히 하나의 부분집합에만 속하도록 하면서 두 부분집합에 속한 원소들의 합이 같아지게 해야 한다.

익명의 제보에 따르면, 위 문제는 다항 시간에 풀기 어렵다(뭐 그런 류의 이야기)고 한다. 그래서 우리는 문제를 바꾸기로 했다. 이제 당신이 정수들 중 절반을 직접 정할 수 있다!

이 문제는 3단계로 이루어진 인터랙티브 문제이다. 1단계에서 당신은 서로 다른 정수 \mathbf{N}개를 선택한다. 2단계에서 당신이 1단계에서 고른 정수들과도 서로 다르고, 서로 간에도 모두 다른 정수 \mathbf{N}개가 추가로 주어진다. 3단계에서 당신은 이 2\mathbf{N}개의 정수를 두 부분집합으로 나누어 두 부분집합의 합이 같아지도록 해야 한다. 모든 2\mathbf{N}개의 정수는 1 이상 10^9 이하이며, 이들의 총합이 짝수라는 것이 보장된다.