Problem: Super Maria
Want to try solving this problem? You can submit your code online if you log in or register.
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
- 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.
5 10 18 41
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
She will now have collected all the coins and ran a total distance of
9 + 4 + 13 = 26
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.