2015 Canadian Computing Olympiad
Day 1, Problem 1 - Hungry Fox
It's dinner time for your pet fox! His meal consists of N crackers, with the i-th cracker having a temperature of Ti degrees Celsius. He also has a large dish of water, which has a temperature of W degrees Celsius.
After taking an initial sip of water, your fox begins his meal. Every time he eats a cracker, its tastiness is equal to the absolute difference between its temperature, and the temperature of the last thing he ate or drank (be it the previous cracker he ate, or a sip of water, whichever he consumed most recently). He can drink some water whenever he wants, and can eat the crackers in any order.
Depending on the order in which your fox eats and drinks, the total tastiness of the crackers consumed may vary. What are the minimum and maximum values it can have?
The first line contains two integers, N (1 ≤ N ≤ 100,000) and W (0 ≤ W ≤ 109), representing the number of crackers and the water's temperature. On the next N lines, there is one integer, Ti (0 ≤ Ti ≤ 109 for 1 ≤ i ≤ N), representing the temperature of the i-th cracker.
For at least 30% of the marks for this problem, W = 0.
The output is one line containing two integers: the minimum and maximum total tastiness your fox can experience during his meal, respectively.
3 20 18 25 18
To minimize the total tastiness, the fox might drink water, eat the first cracker, eat the third cracker, drink more water, and finally eat the second cracker. He will then experience temperatures of 20, 18, 18, 20, and 25 degrees Celsius, and the crackers will have tastiness values of 2 + 0 + 5 = 7.
To maximize the total tastiness, the fox might drink water, and then eat the crackers in order. He will then experience temperatures of 20, 18, 25, and 18 degrees Celsius, and the crackers will have tastiness values of 2 + 7 + 7 = 16.
Point Value: 12 (partial)
Time Limit: 2.00s
Memory Limit: 256M
Added: Jun 05, 2015
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3