레이팅 미적용설명
올해 농부 존의 소 12마리가 겨울 무림픽 대회에 참가하며, 각 소는 1 이상 1,000,000 이하의 정수 기량 수치를 갖는다.
농부 존은 이들을 3마리씩 4팀으로 나누어, 팀들의 총 기량이 어느 정도 "균형" 잡히게 하고 싶다 (팀의 기량 수치는 그 팀에 속한 소들의 기량 수치의 합이다). 구체적으로, 팀 기량 수치의 최댓값과 최솟값을 각각 S와 s라 할 때 S - s를 최소화하고 싶다. 이렇게 하면 가장 강한 팀과 가장 약한 팀 사이의 격차가 최대한 작아진다.
농부 존이 S - s의 가능한 최솟값을 구하는 것을 도와주시오.
제약
입력 형식
첫째 줄부터 12번째 줄까지, 각 줄에 소 한 마리의 기량 수치가 주어진다.
출력 형식
S - s의 가능한 최솟값을 출력한다.
Standard input / output
This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:
입력을 읽을 파일
bteams.in · 출력을 쓸 파일 bteams.out예제 1
입력
1
2
3
4
5
6
7
8
9
10
11
12출력
1설명
Output details: One solution: (12,1,7), (9,8,3), (10,5,4), (11,2,6) -- skills 20, 20, 19, 19.
문제 정보
riseoj 작성
출처 올림피아드 > USACO > 2013-2014 > January > Bronze
태그