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

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:

- The amazing ability to run to the left.
- The amazing ability to run to the right.
- The ordinary ability to instantly transport herself from any
position to a teleport receiver. After Maria teleports to a receiver,
it is depleted of energy and can not be used again. Hence, Maria can teleport
to each receiver at most once.

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).

- The first line of input will contain two integers C and R: the number
of coins and the number of receivers on the platform.
- The second line of input will contain C integers, which are in
ascending order. The ith integer is the distance (in metres) of the ith
coin from the left edge of the platform.
- The third line of input will contain R integers, which are in ascending
order. The ith integer is the distance (in metres) of the ith receiver from the
left edge of the platform.

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

4 2 5 10 18 41 14 32

26

Maria can do the following:

- Teleport to the receiver at 32m
- Run right to reach the coin at 41m
- Teleport to the receiver at 14m
- Run right to the coin at 18m
- Run left to the coins at 10m and then 5m

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.

- For Subtask 1 (15 pts), C ≤ 100, R ≤ 2, L ≤ 1,000,000.
- For Subtask 2 (25 pts), C ≤ 100, R ≤ 100, L ≤ 1,000,000.
- For Subtask 3 (25 pts), C ≤ 1000, R ≤ 1000, L ≤ 1,000,000,000.
- For Subtask 4 (35 pts), C ≤ 100,000, R ≤ 100,000, L ≤ 1,000,000,000.

Privacy
statement

© Australian Mathematics Trust 2001-2021

Page generated: 1 December 2021, 10:55am AEDT