시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1.5 초 (하단 참고) | 512 MB | 166 | 49 | 40 | 32.787% |
Alice와 Bob은 수가 적힌 카드를 이용한 게임을 즐겨한다.
지금 Bob은 $n$장의 카드, Alice는 $m$장의 카드를 갖고 있고, 각 카드에는 양의 정수가 적혀있다.
두 사람은 각자 자신이 가진 카드 중 $k$장씩을 선택하여 이에 적힌 $k$개의 정수를 더하여 본인의 점수를 계산하기로 했다. 이 때 Bob의 점수를 $B$, Alice의 점수를 $A$라 하자. 이 게임은 두 사람이 어떤 카드를 선택하는지에 따라 $B$, $A$ 값이 바뀌므로 두 사람은 문득 $|B - A|$의 최솟값과 최댓값이 궁금해졌다.
예를 들어 $k = 2$ 이고 Bob은 $[2, 3, 5]$가 적힌 카드를, Alice는 $[1, 4, 8, 9]$가 적힌 카드를 가지고 있다고 하자.
입력으로 $k$와 두 사람이 가진 카드에 적힌 수들이 주어졌을 때, 달성 가능한 $|B - A|$의 최솟값과 최댓값을 구해보자.
첫 줄에 테스트 케이스의 수 $T$가 주어진다.
각 케이스의 입력은 세 줄에 나누어 주어진다. 첫 줄에 $n$, $m$, $k$가 공백으로 구분되어 주어진다. 둘째 줄에 Bob이 가진 카드에 적힌 수 $n$개가 공백으로 구분되어 주어진다. 셋째 줄에 Alice가 가진 카드에 적힌 수 $m$개가 공백으로 구분되어 주어진다.
각 테스트 케이스의 정답을 최솟값, 최댓값 순으로 공백으로 구분하여 각 줄에 출력한다.
4 3 4 2 2 3 5 1 4 8 9 3 4 3 2 3 5 1 4 8 9 5 5 3 1 2 1 2 3 3 2 3 2 1 2 2 2 2022 2021 2022 2000
0 12 3 11 0 4 21 21
예제 1-2: 본문에서 다루었다.
예제 3: 이 경우 Bob, Alice가 각각 $(1, 2, 3)$을 골라 $6$점씩 달성하면 점수 차이의 최솟값은 $0$이다. Bob이 $(1, 1, 2) = 4$점, Alice가 $(2, 3, 3) = 8$점을 달성하면 최댓값은 $4$가 된다.
예제 4: 이 경우 Bob이 달성 가능한 점수는 $(2022+2021)$이고 Alice가 달성 가능한 점수는 $(2022+2000)$이므로 두 점수 차이의 최솟값과 최댓값은 $21$이다.