Problem J
Cow Crane

Photo by Stuart Heath

Farmer Laura has a barn. In her barn, she has two cows, Monica and Lydia. Monica and Lydia love food, and they are quite lazy. For most of the day they chill out in the barn, waiting for Laura to come serve them a nice meal. Farmer Laura is always very precise about when to serve them food, so Monica and Lydia know exactly when to expect food, the same time every day.

This might sound surprising to you but there’s a problem. Farmer Laura needs your help. She will be replacing some planks in the floor of the barn, which means that the cows have to be moved temporarily from their favorite spots. Since the cows are infinitely lazy, they refuse to walk themselves. Farmer Laura has rented an excellent tool to resolve this issue – a cow crane, designed and crafted specifically for the cow’s comfort.

We visualize the barn as a one-dimensional line. The cow crane starts at time $t = 0$ at position $x = 0$, and it can move one distance unit per second. The crane can only carry one cow at a time, but it may pick up and drop off a cow as many times as necessary. Monica’s current location is at $x = m$, and Lydia is located at $x = l$. Monica will be moved to the temporary location at $x = M$ and Lydia to $x = L$. Monica and Lydia always have their daily meal $t_ m$ and $t_ l$ seconds into the day, so the cows had better be in their respective temporary locations exactly by these times. You may assume that it takes no time for the crane to pick up or drop off a cow and that the two cows can be at the same position at the same time.


Farmer Laura would like to know if she can move the cows so that both of them are in place at their temporary location no later than their daily meal occurs.


Input consists of three lines. The first line consists of two integers $m$ and $l$, the current positions of the cows. The second line consists of two integers $M$ and $L$, the new positions of the cows. The third line consists of two integers $t_ m$ and $t_ l$, the time at which the two cows will be served their daily meal. It is guaranteed that $-10^8 \leq m, l, M, L \leq 10^8$ and $1 \leq t_ m, t_ l \leq 10^8$. It is also guaranteed that both cows will actually move, i.e., $m \not= M$ and $l \not= L$.


Output should consist of a single word. Print “possible” if it is possible to move both cows before they are served their daily meal. Otherwise, print “impossible”.

Sample Input 1 Sample Output 1
-1 1
-2 2
6 6
Sample Input 2 Sample Output 2
-1 1
-2 2
5 5
Sample Input 3 Sample Output 3
-1 1
1 -1
3 5
Sample Input 4 Sample Output 4
0 1
2 3
6 3
CPU Time limit 1 second
Memory limit 1024 MB
Statistics Show
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in