The King's Assessment

0

0 votes
Medium
Problem

The King of the Saracens is quite impressed with the Saboteurs. He tests their mettle further with the following task:-

There exists a linked list that consists of K nodes. The nodes of the path are numbered from 1 to K. Two pointers start moving at time t = 0 (seconds) with speeds A and B (nodes/second). The slower pointer starts at node 1 and the faster pointer starts at node D + 1. The task is to print the minimum integer L denoting the number of nodes in a loop that needs to be attached to node K such that the two pointers never meet. If no such L exists print “Impossible” (without quotes). Note that node K is not part of the loop.

Note that the two pointers are considered to have met each other if and only if they are at the same node at the same integer time t. Also, note that L must be at least 2.

Solve the problem and earn the trust of the King of the Saracens!

Input Format

The first and only line contains 4 integers A, B, K and D as described in the problem statement

Output Format

Print a single integer L (>= 2) or “Impossible” (without quotes) denoting the answer.

Constraints

1A,B1012

0D<K1018

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

The constructed linked list has 4 nodes with nodes 1 and 2 in the straight path, nodes 3 and 4 in a loop with node 3 attached to node 2. Let the pointer of speed 1 be denoted by P1 and let the pointer of speed 3 be denoted by P2.

At time t = 0, P1 is at node 1 and P2 is at node 2.

At time t = 1, P1 is at node 2 and P2 is at node 3.

At time t = 2, P1 is at node 3 and P2 is at node 4.

At time t = 3, P1 is at node 4 and P2 is at node 3.

They never meet! Hence, the answer.

Editor Image

?