AIOC Banner

Problem: Super Maria

Want to try solving this problem? You can submit your code online if you log in or register.

Super Maria

Time Limit: 1 second
Memory Limit: 128 MB
Input File: standard input
Output File: standard output

Maria is an electrician who lives in the Fungus Republic, where every few years disaster strikes and Maria always ends up being the one who must restore order. This year her evil sister Waria has kidnapped her Prince Nectarine, so she is once again on a long and confusing quest to save him.

Maria is called Super Maria by her friends because she posseses three super-powers:

For some unexplained reason, Maria's quest requires her to collect a sequence of gold coins which are conveniently lying on a flat straight line (a platform). There is also at least one teleport receiver on this platform. Maria needs to first teleport to one of the receivers as she is not initially on the platform, then use her three super-powers to move around and collect all the coins. Maria doesn't like running around on a platform collecting things like some silly plumber, so she has asked you to write a program to calculate the minimum total distance she must run.

Maria doesn't care which receiver she starts from, or where she ends up on the platform after collecting all the coins. No two coins will be at the same position and no two receivers will be at the same position (however a coin and a receiver may share a position).



Output should consist of one line containing one integer: the minimum distance Maria must run in order to collect all the coins.

Sample Input

4 2
5 10 18 41
14 32

Sample Output



Maria can do the following:

  1. Teleport to the receiver at 32m
  2. Run right to reach the coin at 41m
  3. Teleport to the receiver at 14m
  4. Run right to the coin at 18m
  5. Run left to the coins at 10m and then 5m
She will now have collected all the coins and ran a total distance of 9 + 4 + 13 = 26 metres.


For all subtasks, C ≥ 1, R ≥ 1 and all receiver and coin positions are integers between 0 and L (the length of the platform) inclusive.


Privacy statement
© Australian Mathematics Trust 2001-2024

Page generated: 13 April 2024,  7:35am AEST