Being a fan of contemporary architecture, Farmer John has built a new barn in the shape of a perfect circle. Inside, the barn consists of a ring of n rooms, numbered clockwise from 1 \ldots n around the perimeter of the barn (3 \leq n \leq 1,000). Each room has doors to its two neighboring rooms, and also a door opening to the exterior of the barn.

Farmer John wants exactly r_i cows to end up in room i (1 \leq r_i \leq 1,000,000). To herd the cows into the barn in an orderly fashion, he plans to unlock k exterior doors (1 \leq k \leq 7), allowing the cows to enter through only those doors. Each cow then walks clockwise through the rooms until she reaches a suitable destination. Farmer John wants to unlock the exterior doors that will cause his cows to collectively walk a minimum total amount of distance after entering the barn (they can initially line up however they like outside the k unlocked doors; this does not contribute to the total distance in question). Please determine the minimum total distance his cows will need to walk, if he chooses the best k such doors to unlock.

Problem credits: Brian Dean

#3964 upload 5 done 1 how_to_reg 1

Circular Barn timer 2s memory 512MB

#3964

Circular Barn 2s 512MB