Problem L
Aquarium
The aquarium at which you work is hoping to expand its meagre selection of aquatic life, but lacks the funds to do so. You have been tasked to help promote the aquarium by taking photos of the two exhibits. Taking the first photo went swimmingly, because the catfish were very cooperative. For the piranhas, you have an arrangement of piranhas in mind that will look great on the photo. However, the only way to get the piranhas to move is by recklessly sticking your finger into the water to lure the piranhas. Your goal is to move the piranhas to the desired positions as quickly as possible without losing your finger in the process.
The piranha exhibit can be divided into positions $1,\ldots ,n$ from left to right. The exhibit contains $k$ piranhas and every position is occupied by at most one piranha. You can stick your finger into any unoccupied position. This will lure the nearest piranha to the left of your finger and the nearest piranha to the right of your finger. These piranhas will swim towards your finger, moving forward one position per second. All other piranhas simply stay in place. A piranha will bite your finger if it reaches the same position, so you must pull your finger away before this happens. Pulling your finger away and sticking it into a different position does not take any time.
For example, suppose there are piranhas at positions $2$, $7$ and $9$. If you stick your finger into the water at position $4$, the piranhas will be at positions $3$, $6$ and $9$ after one second. You now have to pull your finger away to prevent the piranha at position $3$ from biting your finger one second later. If you now stick your finger into the water at position $1$, only the piranha at position $3$ will move and will end up at position 2 after one second.
Input
-
One line containing two integers $n$ ($1\leq n\leq 1000$), the number of positions, and $k$ ($1\leq k\leq n$), the number of piranhas.
-
One line containing $k$ integers $1\leq p_1<\ldots <p_ k\leq n$, the current positions of the piranhas.
-
One line containing $k$ integers $1\leq d_1<\ldots <d_ k\leq n$, the desired positions of the piranhas.
Output
Output the minimum number of seconds needed to get all of the piranhas at the desired positions. If it is impossible to do so, output “impossible”.
| Sample Input 1 | Sample Output 1 |
|---|---|
9 3 3 7 9 3 5 9 |
4 |
| Sample Input 2 | Sample Output 2 |
|---|---|
8 3 1 5 8 2 4 7 |
impossible |
| Sample Input 3 | Sample Output 3 |
|---|---|
20 6 1 4 7 10 13 20 2 5 8 11 14 17 |
17 |
