레이팅 미적용설명
농부 존(Farmer John)은 방금 N개 (1 <= N <= 20)의 건초 더미를 새로 배송받았다. 더미 i의 크기는 S_i (1 <= S_i <= 100)이다. 존은 이 더미들을 세 헛간에 최대한 공정하게 나누고 싶어 한다.
신중히 고민한 끝에, FJ는 건초 더미의 "공정한" 분배란 가장 큰 몫을 최대한 작게 만드는 것이라고 결론지었다. 즉, B_1, B_2, B_3가 각각 헛간 1, 2, 3에 놓인 모든 더미의 크기 합이라면 (B_1 >= B_2 >= B_3), FJ는 B_1을 최대한 작게 만들고 싶다.
예를 들어 크기가 2 4 5 8 9 14 15 20인 8개의 더미가 있다면, 공정한 해는 헛간 1: 2 9 15 (B_1 = 26), 헛간 2: 4 8 14 (B_2 = 26), 헛간 3: 5 20 (B_3 = 25)이다.
건초 더미의 공정한 분배에서 B_1의 값을 구하는 것을 FJ에게 도와주자.
제약
입력 형식
첫째 줄: 더미의 수 N.
둘째 줄부터 1+N번째 줄까지: i+1번째 줄에 i번째 더미의 크기 S_i가 주어진다.
출력 형식
건초 더미의 공정한 분배에서의 B_1 값을 출력한다.
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:
입력을 읽을 파일
baleshare.in · 출력을 쓸 파일 baleshare.out예제 1
입력
8
14
2
5
15
8
9
20
4출력
26문제 정보
riseoj 작성
출처 올림피아드 > USACO > 2011-2012 > January > Silver
태그