레이팅 미적용농부 존의 원형 헛간과 관련된 지난 소동을 겪었다면, 그가 비전통적 건축에 대해 교훈을 얻었으리라 생각할 것이다. 하지만 그는 각 방에 여러 마리의 소를 들여보내면 (앞 문제의) 원형 헛간을 여전히 제대로 운영할 수 있다고 생각한다. 다시 정리하면, 헛간은 둘레를 따라 시계 방향으로 \(1 \ldots n\) 번호가 붙은 \(n\)개의 방이 고리 모양으로 배치되어 있다 (\(3 \leq n \leq 100\)). 각 방에는 이웃한 두 방으로 통하는 문과, 헛간 바깥으로 통하는 문이 하나씩 있다.
농부 존은 방 \(i\)에 정확히 \(r_i\)마리의 소가 들어가기를 원한다 (\(1 \leq r_i \leq 1,000,000\)). 소들을 질서 있게 헛간으로 몰기 위해, 그는 외부 문 \(k\)개를 열어 (\(1 \leq k \leq 7\)) 소들이 그 문들로만 들어오게 할 계획이다. 각 소는 적절한 목적지에 도달할 때까지 방들을 시계 방향으로 걸어간다. 농부 존은 소들이 헛간에 들어온 뒤 걷는 총거리가 최소가 되도록 외부 문들을 열고 싶다 (열린 \(k\)개의 문 밖에서는 소들이 원하는 대로 줄을 설 수 있으며, 이는 여기서 말하는 총거리에 포함되지 않는다). 가장 좋은 문 \(k\)개를 열었을 때 소들이 걸어야 하는 최소 총거리를 구하여라.
출제자: Brian Dean
출제자: Brian Dean
입력의 첫째 줄에 \(n\)과 \(k\)가 주어진다. 다음 \(n\)개의 줄에 \(r_1 \ldots r_n\)이 주어진다.
소들이 이동해야 하는 최소 거리를 출력한다.
cbarn2.in · 출력을 쓸 파일 cbarn2.out6 2
2
5
4
2
6
214Farmer John can unlock doors 2 and 5. 11 cows enter at door 2 and walk a total
distance of 8 to get to rooms 2, 3, and 4. 10 cows enter at door 5 and walk a
total distance of 6 to get to rooms 5, 6 and 1.
riseoj 작성
출처 올림피아드 > USACO > 2015-2016 > February > Gold