Arranging Seats
Time limit2sMemory limit128 MB
Given seat positions with scores, compute the minimum cost to rearrange computers (with a lift/place cost and per-step carrying cost for up to two items) so the row becomes a rotation of the sorted score sequence.
- Level
Hard8 of 10
- Topics
- Greedy, Math, Simulation
- Solved
- No attempts yet
Problem
There are n students sitting at desks arranged in a line, and each student has a score. A seating arrangement is valid if it can be obtained by sorting the scores in nondecreasing order and then rotating that sorted array. Students with the same score only need to be adjacent, and their relative order does not matter.
For example, for the score array {10 20 20 30}, all of {10 20 20 30}, {20 20 30 10}, {20 30 10 20}, and {30 10 20 20} are valid seating arrangements. However, {30 20 20 10} is not valid because it is not a rotation of the nondecreasing array.
The grading results arrived late, after all students had gone to sleep, so the assistant must move the students' computers to prepare the next day's seating arrangement.
The assistant has only two arms, so at most two computers can be carried at once. Moving one position while carrying computers costs force equal to the number of computers being carried. Also, lifting one computer from a desk costs 10 force, and placing one computer on a desk costs 10 force.
Given the scores in the current seating order, compute the minimum force needed to make a valid seating arrangement.
Input
The first line contains the number of students n. (2 <= n <= 400)
The second line contains the students' scores in their current seating order. Each score is a positive integer not exceeding 2,000,000.
Output
Print the minimum force needed to make a valid seating arrangement.