Canadian Computing Olympiad: 2015 Day 1, Problem 1
It's dinner time for your pet fox! His meal consists of crackers, with the cracker having a temperature of degrees Celsius. He also has a large dish of water, which has a temperature of 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. 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, () and (), representing the number of crackers and the water's temperature. On the next lines, there is one integer, ( for ), representing the temperature of the cracker.
For at least 30% of the marks for this problem, .
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
Output for Sample Input
Explanation of Output for Sample Input
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 .
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 .