레이팅 미적용현대 건축의 팬인 농부 존은 완벽한 원 모양의 새 헛간을 지었다. 헛간 내부는 둘레를 따라 시계 방향으로 \(1 \ldots n\) 번호가 붙은 \(n\)개의 방이 고리 모양으로 배치되어 있다 (\(3 \leq n \leq 1,000\)). 각 방에는 이웃한 두 방으로 통하는 문과, 헛간 바깥으로 통하는 문이 하나씩 있다.
농부 존은 각 방 \(i\)에 정확히 \(r_i\)마리의 소가 들어가기를 원한다 (\(1 \leq r_i \leq 100\)). 소들을 질서 있게 헛간으로 몰기 위해, 그는 방 하나의 외부 문만 열어 소들이 그 문으로 들어오게 할 계획이다. 각 소는 적절한 목적지에 도달할 때까지 방들을 시계 방향으로 걸어간다. 농부 존은 소들이 걷는 총거리가 최소가 되는 외부 문을 열고 싶다. 가장 좋은 문을 열었을 때 소들이 걸어야 하는 최소 총거리를 구하여라. 소 한 마리가 걷는 거리는 그 소가 통과하는 내부 문의 개수이다.
출제자: Brian Dean
출제자: Brian Dean
입력의 첫째 줄에 \(n\)이 주어진다. 다음 \(n\)개의 줄에 \(r_1 \ldots r_n\)이 주어진다.
소들이 걸어야 하는 최소 총거리를 출력한다.
cbarn.in · 출력을 쓸 파일 cbarn.out5
4
7
8
6
448In this example, the best solution is to let the cows enter through the
door of the room that requires 7 cows.
riseoj 작성
출처 올림피아드 > USACO > 2015-2016 > February > Bronze