원문보기(http://online-judge.uva.es/p/v100/10032.html)

인기도:B(A,B,C), 성공률:낮음(낮음,보통,높음), 레벨:2(1~4)

About TugOfWar

사무실 야유회에서 줄다리기를 하기로 했다. 야유회에 참가한 사람들을 두 편으로 공평하게 나눈다. 모든 사람들이 둘 중 한 편에 참여해야 하며, 두 편의 사람 수는 한 명이 넘게 차이가 나면 안 된다. 그리고 양 편에 속한 사람들 체중의 총합 차를 최소한으로 줄여야 한다.

Input

첫번째 줄에는 테스트 케이스의 수가 입력되고, 그 다음 줄은 빈 줄이다.

각 케이스의 첫번째 줄에는 야유회에 참가한 사람의 수인 n이 입력된다. 그리고 그 밑으로 n줄에 걸쳐서 야유회에 참가한 사람의 체중이 입력된다. 이 값은 1 이상 450 이하의 정수이다. 야유회에 참가하는 사람의 수는 최대 100명이다.

서로 다른 테스트 케이스 사이에는 빈 줄이 하나씩 입력된다.

output

각 테스트 케이스마다 한 줄씩의 결과를 출력하며, 각 줄마다 두 개씩의 정수가 출력된다. 첫번째 수는 한편에 속한 사람들의 체중의 총합, 다른 수는 다른 편에 속한 사람들의 체중의 총합이다. 이 두 값이 서로 다르면 작은 값을 먼저 출력한다.

두 개의 서로 다른 케이스에 대한 결과는 빈 줄로 구분한다.

Sample Input

5

3
100
90
200

6
45
55
70
60
50
75

4
92
56
47
82

5
2
3
4
7
8

4
50
50
100
200

worst case(입력자료 크기로만) 입력은 TugOfWarInput 참조

Sample Output

190 200
175 180
138 139
12 12
150 250

풀이

작성자 사용언어 개발시간 코드
상협 Python 3시간 TugOfWar/남상협
신재동 Python 14분 TugOfWar/신재동
강희경 Python 2일 TugOfWar/강희경
김회영 C 4시간 TugOfWar/김회영
JuNe Python 1시간 Seminar:TugOfWar/JuNe
이승한 C 오래. TugOfWar/이승한
문보창 C++ . TugOfWar/문보창

쓰레드

원문에는 테스트가 너무 적은 것 같아 2개 더 추가합니다. --재동

번역 실수~ 140을 450으로 수정했음 -- 재선

테스트케이스를 하나 더 추가하였습니다. --강희경
테스트의 출력이 틀렸다. 12 12가 아니라 11 13이다. --재동
제가 짠 프로그램에도 그렇게 나오는데, 손으로 풀면 4+8, 2+3+7이렇게 되네요 --강희경
12 12 아닌가요? 총합차이가 최소인데요 -- 재선
12 12가 맞는 것 같군. 그럼 문제가 생각보다 어려워지는데... --재동
이런식의 문제 대략 어려운데;; - 이승한
사람수를 고려안하고 했음. 낭패. ㅠ.ㅠㅋ - 이승한

Retrieved from http://wiki.zeropage.org/wiki.php/TugOfWar
last modified 2021-02-07 05:28:16