GFSSOC '15 Fall Practice P5 - Bruno and Pumpkins

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 32M

Problem types

It's almost Halloween, and that means that Bruno needs to help carve out spooky pumpkins. However, before Bruno starts carving, he first needs to get the pumpkins. Unfortunately, the only place to get super high quality pumpkins is the line of dread. Why is it called the line of dread? Because all the pumpkins grow on a single line, and some years the distances between the pumpkins are … far from favourable. This year, N pumpkins have grown on the line of dread, each located on an integer coordinate from -1000 to 1000, relative to position 0 representing the entrance to the line. Bruno wishes to pick up T pumpkins and put them all in his giant backpack. Obviously, being a true computer scientist, Bruno wants to minimize the distance he needs to walk. Bruno starts at the entrance, but does not need to go back to the entrance after he picks up the pumpkins. Can you figure out the least distance Bruno needs to walk in order to pick up T pumpkins?

Input Specification

The first line contains a single integer N. (1 \le N \le 1000)

The second line contains a single integer T. (1 \le T \le N)

The next N lines each contain one integer, the coordinate position of a pumpkin. The coordinate will not be 0. It is also guaranteed there are no two pumpkins in the same coordinate.

Note: It is not guaranteed the pumpkins are given in sorted order.

Output Specification

Output a single integer, the minimum distance Bruno needs to walk, given he starts at coordinate 0 and it does not matter where he ends at.

Sample Input


Sample Output


Explanation for Sample Output

The line of dread looks as follows, with the blue diamond representing the entrance:

One optimal way of getting 3 pumpkins would be to walk to the pumpkin at coordinate -3, then to the pumpkin at coordinate 2, then to the pumpkin at coordinate 4. This gives the total distance of:

\displaystyle |(-3)-0| + |2-(-3)| + |4-2| = 10


There are no comments at the moment.