Once Opened, You Can't Stop
Time limit2sMemory limit128 MB
Choose one integer per flavor within its given range so the sum of absolute changes between consecutive picks is minimized, and output the values.
- Level
Medium7 of 10
- Topics
- Dynamic programming, Greedy, Intervals, Two pointers
- Solved
- No attempts yet
Problem
A monkey that escaped from a zoo is about to eat several new flavors of Pringles in order. For each flavor, the monkey must choose an integer addiction-stress value inside the range assigned to that flavor.
Whenever the stress value changes, the monkey's expected lifespan decreases by the absolute difference between the previous value and the new value. For example, changing the value from 5 to 3 or to 7 decreases the expected lifespan by 2 years.
Before eating the first flavor, the monkey may choose any initial stress value for free. Given N flavors that must be eaten in the input order, minimize the total decrease in expected lifespan and output one stress value chosen for each flavor.
Input
The first line contains the number of flavors N. (1 <= N <= 100,000)
Each of the next N lines contains two integers s_i and e_i. For the i-th flavor, the addiction-stress value must be at least s_i and at most e_i. (1 <= s_i <= e_i <= 200)
The flavors must be eaten in the order given by the input.
Output
Print the minimum possible decrease in expected lifespan on the first line.
Then print N more lines. The i-th of these lines must contain the addiction-stress value chosen for the i-th flavor. If several choices achieve the minimum, you may print any one of them.