본문 바로가기

PKU & UVa problems/Translated problem

UVa 562. Dividing Coins.

  동전 나누기

일반적으로 구리선은 네덜란드인이 발명한 것으로 알려져 있습니다. 두 네덜란드 사람이 구리로 만들어진 동전을 두고 싸우고 있었습니다. 그들은 동전을 매우 가지고 싶었기 때문에 싸움은 꽤나 난폭하게 벌어졌고 결국 동전을 매우 세게 양쪽에서 잡아당기는 바람에 구리선이 만들어지게 되었다고 합니다.


그러나 싸운 뒤의 일은 잘 알려져 있지 않은데요, 그 뒤에 두 사람은 동전으로 차있는 가방을 둘 중 한 명에게 주려고 했습니다. 가방 안의 들어있는 동전들은 똑같이 나눌순 없었습니다. 첫 번째 사람은 그 둘 모두가 아주 사소한 것까지 똑같이 나누고 싶어한다는 점에서 분배량이 똑같지 않다는 것을 참을 수 없었습니다. 요즘 들어서 동전 하나때문에 싸운다는것은 찾아보기 어려운 일이지만,  가능한한 최대한 공평하도록 똑같이 분배하는 것은 영원히 불가능한 일로 남을 것 같습니다.


이것이 이 문제의 전부입니다.두 사람에게 가방의 동전을 어떻게 나누는게 가장 공평할지를 모든 사람이 한 번에 알 수는 없습니다. 당신은 이 문제를 어떻게 풀지 이제 요청을 받았습니다.


최대 100개의 동전이 있는 가방을 가지고 시작하는데, 가장 두 사람에게 공평하게 분배하는 방법을 결정하면 됩니다. 이 말은, 각자에게 다른 양의 동전을 주는 것은 최소한으로 되어야 한다는 것입니다. 동전은 1센트부터 500센트까지의 가치를 지니고 있습니다. 단, 동전을 쪼개는 것은 안됩니다.

입력

n개의 문제를 나타내고, 그 밑에 문제가 n번 나옵니다:
  • 양정수 m(m ≤ 100)개로 이루어진 줄은 가방 안의 동전의 개수를 나타냅니다.                        
  • m개의 숫자들이 한 칸씩 사이에 두고 적히고, 각 숫자들은 동전의 가치를 나타냅니다.                                               

출력

n개의 줄로 출력합니다. 각 줄은 각각의 가방에 대해서 두 사람이 동전을 나눠가질때 발생하는 최소한의 차이를 양수로 나타냅니다.

입력 예시

2
3
2 3 5
4
1 2 4 6

출력 예시

0
1



Miguel A. Revilla 
1998-03-10

'PKU & UVa problems > Translated problem' 카테고리의 다른 글

PKU 2871. A Simple Question of Chemistry  (0) 2010.02.26
PKU 3589. Number-guessing Game  (0) 2010.02.01
PKU 3372. Candy Distribution  (6) 2009.11.25
PKU 3224. Go for Lab Cup!  (3) 2009.11.09
PKU 1989. The Cow Lineup  (2) 2009.10.27