Optimal Knocking Strategy for Flubber Flow Estimation

Your hometown has hired contractors – including you – to manage its municipal pipe network built to supply Flubber to every home. Although Flubber’s use is still mysterious, you must now determine the rate at which it flows. You have a single opaque pipe of length \(l\) meters, and you may initiate the Flubber flow at a time of your choice. The Flubber flows at a constant real speed \(v\) (in meters/second), satisfying \(v_1 \le v \le v_2\). You are allowed to knock on the pipe at any point along its length (i.e. anywhere in the closed interval \([0,l]\)). When you knock, you immediately hear whether the Flubber has reached that point.

Your aim is to estimate the flow speed \(v\) with a maximum absolute error of \(\frac{t}{2}\) meters/second. However, you cannot knock arbitrarily fast. Your first knock may occur only at least \(s\) seconds after starting the flow, and there must be at least \(s\) seconds between any two knocks.

You are to design a strategy that minimizes the number of knocks required in the worst case to achieve the desired estimation accuracy. Note that in some cases the estimation might be impossible (for example, if the Flubber reaches the end of the pipe too quickly). More precisely, consider the following:

• You may only perform a knock at time \(T = k \cdot s\) for some positive integer \(k\) (i.e. knocks at \(s, 2s, 3s, \ldots\)).
• When you knock at time \(T\) at position \(x\), you hear a positive response if and only if the Flubber has reached that point, i.e. if \(\frac{x}{v} \le T\). Equivalently, you obtain a positive response if \(v \ge \frac{x}{T}\) and a negative response otherwise.
• You may choose the knock positions adaptively. In a well‐designed strategy, a knock at time \(T\) is used to test whether \(v\) is above or below a certain threshold \(C\) by knocking at position \(x = C\cdot T\). Note that such a knock is only valid provided \(x \le l\), i.e. \(C \le \frac{l}{T}\).
• Before any knocks, your knowledge of \(v\) is that it lies in the interval \([v_1,v_2]\). To achieve an estimate with absolute error at most \(\frac{t}{2}\), you must reduce the uncertainty interval to have length at most \(t\). If \(v_2-v_1 \le t\) then no knocks are needed.
• If at any point the maximum threshold you can test is lower than \(v_2\) (in particular, note that at the first knock you have at most \(\frac{l}{s}\) as a threshold), then it may be impossible to design a strategy. In fact, if \(v_2 > \frac{l}{s}\) then even a knock at the far end \(x=l\) is trivial, and estimation is impossible.

Your task is: Given the pipe length \(l\), the speed bounds \(v_1\) and \(v_2\), the accuracy parameter \(t\), and the minimal interval \(s\) between knocks, determine the minimum number of knocks needed in the worst-case (using an optimal adaptive strategy) to estimate \(v\) with absolute error at most \(\frac{t}{2}\), or output impossible if accurate estimation is not feasible.

Hint: An optimal strategy uses binary search. In particular, if the initial uncertainty \(v_2-v_1\) is greater than \(t\), then at least \(n = \lceil \log_2\frac{v_2-v_1}{t}\rceil\) knocks are required. However, note that feasibility also demands that \(v_2 \le \frac{l}{s}\); otherwise, the test is trivial even at the first knock.

inputFormat

The input consists of a single line containing five space‐separated numbers:

• l — the length of the pipe in meters,
• v1 — the minimum possible speed (in m/s),
• v2 — the maximum possible speed (in m/s),
• t — the accuracy parameter (the final estimate must be within \(\frac{t}{2}\) m/s of the true speed),
• s — the minimum number of seconds before the first knock and the required gap between knocks.

All numbers can be considered as real numbers. You may assume that \(v1 \le v2\), and that \(l, t, s\) are positive.

outputFormat

Output a single line. If it is impossible to estimate the speed with the given constraints, output impossible (without quotes). Otherwise, output the minimum number of knocks required in the worst-case to achieve the estimation accuracy.

Note: If the initial uncertainty \(v2-v1\) is already at most \(t\), then no knocks are needed and the answer is 0.

sample

10 1 10 1 1

4