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 T_i 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?

Input Format

The first line contains two integers, N (1 ≤ N ≤ 100,000) and W (0 ≤ W ≤ 10⁹), representing the number of crackers and the water's temperature. On the next N lines, there is one integer, T_i (0 ≤ T_i ≤ 10⁹ for 1 ≤ i ≤ N), representing the temperature of the i-th cracker.

For at least 30% of the marks for this problem, W = 0.

Output Format

The output is one line containing two integers: the minimum and maximum total tastiness your fox can experience during his meal, respectively.

Sample Input

3 20
18
25
18

Sample Output

7 16

Explanation

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.

All Submissions
Best Solutions

Point Value: 12 (partial)
Time Limit: 2.00s
Memory Limit: 256M
Added: Jun 05, 2015
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)