Aroma's Search
Contest: Codeforces Round 614 (Div. 1)
Difficulty rating: 1700
Tags: brute force, constructive algorithms, geometry, greedy, implementation

With a new body, our idol Aroma White (or should we call her Kaori Minamiya?) begins to uncover her lost past through the OS space.

The space can be considered a 2D plane, with an infinite number of data nodes, indexed from $$$0$$$, with their coordinates defined as follows:

- The coordinates of the $$$0$$$-th node is $$$(x_0, y_0)$$$
- For $$$i > 0$$$, the coordinates of $$$i$$$-th node is $$$(a_x \cdot x_{i-1} + b_x, a_y \cdot y_{i-1} + b_y)$$$

Initially Aroma stands at the point $$$(x_s, y_s)$$$. She can stay in OS space for at most $$$t$$$ seconds, because after this time she has to warp back to the real world. She doesn't need to return to the entry point $$$(x_s, y_s)$$$ to warp home.

While within the OS space, Aroma can do the following actions:

- From the point $$$(x, y)$$$, Aroma can move to one of the following points: $$$(x-1, y)$$$, $$$(x+1, y)$$$, $$$(x, y-1)$$$ or $$$(x, y+1)$$$. This action requires $$$1$$$ second.
- If there is a data node at where Aroma is staying, she can collect it. We can assume this action costs $$$0$$$ seconds. Of course, each data node can be collected at most once.

Aroma wants to collect as many data as possible before warping back. Can you help her in calculating the maximum number of data nodes she could collect within $$$t$$$ seconds?

Input format:
The first line contains integers $$$x_0$$$, $$$y_0$$$, $$$a_x$$$, $$$a_y$$$, $$$b_x$$$, $$$b_y$$$ ($$$1 \leq x_0, y_0 \leq 10^{16}$$$, $$$2 \leq a_x, a_y \leq 100$$$, $$$0 \leq b_x, b_y \leq 10^{16}$$$), which define the coordinates of the data nodes.

The second line contains integers $$$x_s$$$, $$$y_s$$$, $$$t$$$ ($$$1 \leq x_s, y_s, t \leq 10^{16}$$$) – the initial Aroma's coordinates and the amount of time available.

Output format:
Print a single integer — the maximum number of data nodes Aroma can collect within $$$t$$$ seconds.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In all three examples, the coordinates of the first $$$5$$$ data nodes are $$$(1, 1)$$$, $$$(3, 3)$$$, $$$(7, 9)$$$, $$$(15, 27)$$$ and $$$(31, 81)$$$ (remember that nodes are numbered from $$$0$$$).

In the first example, the optimal route to collect $$$3$$$ nodes is as follows:

- Go to the coordinates $$$(3, 3)$$$ and collect the $$$1$$$-st node. This takes $$$|3 - 2| + |3 - 4| = 2$$$ seconds.
- Go to the coordinates $$$(1, 1)$$$ and collect the $$$0$$$-th node. This takes $$$|1 - 3| + |1 - 3| = 4$$$ seconds.
- Go to the coordinates $$$(7, 9)$$$ and collect the $$$2$$$-nd node. This takes $$$|7 - 1| + |9 - 1| = 14$$$ seconds.

In the second example, the optimal route to collect $$$2$$$ nodes is as follows:

- Collect the $$$3$$$-rd node. This requires no seconds.
- Go to the coordinates $$$(7, 9)$$$ and collect the $$$2$$$-th node. This takes $$$|15 - 7| + |27 - 9| = 26$$$ seconds.

In the third example, Aroma can't collect any nodes. She should have taken proper rest instead of rushing into the OS space like that.

Example input:
1 1 2 3 1 0
2 4 20

Example output:
3

Example input:
1 1 2 3 1 0
15 27 26

Example output:
2

Editorial:
First, keep a list of "important" nodes (nodes that are reachable from the starting point with $$$t$$$ seconds), and denote this list $$$[(x_1, y_1), (x_2, y_2), \ldots, (x_k, y_k)]$$$. Since $$$a_x, a_y \geq 2$$$, there are no more than $$$\log_2(t)$$$ important nodes (in other words, $$$k \leq \log_2(t))$$$.
In an optimal route, we must first reach a data node in fastest time possible. Suppose that we reach node $$$z$$$ first, and we now have $$$t'$$$ seconds left.
Let's denote $$$d(i, j)$$$ the time required to travel from the $$$i$$$-th node to the $$$j$$$-th node. $$$d(i, j)$$$ is also the Manhattan distance between the $$$i$$$-th and the $$$j$$$-th node – in other words, $$$d(i, j) = |x_j - x_i| + |y_j - y_i|$$$. Since $$$x_i \geq x_{i-1}$$$ and $$$y_i \geq y_{i-1}$$$, we have $$$d(u, v) + d(v, w) = d(u, w)$$$ for all $$$1 \leq u < v < w \leq k$$$. Therefore, if we consider all the nodes to stay in a line in such a way that $$$x_i = x_{i-1} + d(i-1, i)$$$, the problem is reduced to the following problem:
To solve the above problem, one should notice that it is optimal to collect nodes in a continuous segment. Suppose that we collect all nodes from the $$$l$$$-th to $$$r$$$-th (for some $$$l \leq s \leq r$$$). An optimal route is one of the two below:
• Go from $$$z$$$ to $$$r$$$ and then go to $$$l$$$. The time required for this route is $$$d(r, z) + d(r, l)$$$.
• Go from $$$z$$$ to $$$l$$$ and then go to $$$r$$$. The time required for this route is $$$d(z, l) + d(r, l)$$$.
Therefore, the minimum amount of energy required to collect all the nodes from $$$l$$$-th to $$$r$$$-th is $$$d(r, l) + \min(d(z, l), d(r, z))$$$.
Since $$$k$$$ is small, one can brute-force through all triple of $$$(l, z, r)$$$ such that $$$1 \leq l \leq z \leq r \leq k$$$ and check if $$$t$$$ seconds are enough to go to $$$i$$$-th node and then collect all the nodes from $$$l$$$-th to $$$r$$$-th or not.
The time complexity for that approach is $$$\mathcal{O}(\log_2(t)^3)$$$.
However, we can notice that it's always the most optimal to choose $$$z$$$ as either $$$l$$$ or $$$r$$$, for a few reasons:
• As the aforementioned formula, either $$$d(z, l)$$$ or $$$d(r, z)$$$ will be counted twice (one there, and one within $$$d(r, l)$$$, so having it reduced to $$$0$$$ nullifies the exceeded step.
• The distance from $$$(x_z, y_z)$$$ to $$$(x_s, y_s)$$$ does not break the minimal properties of the endpoint(s) regardless of $$$(x_s, y_s)$$$'s position. We can prove it by considering all possible relative positions of $$$(x_s, y_s)$$$ over the segment (we'll consider the $$$x$$$-coordinates only, $$$y$$$-coordinates will have the same properties, without loss of generality):   If $$$x_s \le x_l$$$, the distance is minimal at $$$z = l$$$.  If $$$x_r \le x_s$$$, the distance is minimal at $$$z = r$$$.  If $$$x_l \le x_s \le x_r$$$, the travelling time in $$$x$$$-coordinates is $$$d(s, z) + d(r, l) + \min(d(z, l), d(r, z))$$$. One can see that $$$d(s, z) + \min(d(z, l), d(r, z)) = \min(d(s, l), d(s, r))$$$, therefore any $$$z$$$ (including the endpoints, of course) is equally optimal. Proof for the above formula is trivial.
• If $$$x_s \le x_l$$$, the distance is minimal at $$$z = l$$$.
• If $$$x_r \le x_s$$$, the distance is minimal at $$$z = r$$$.
• If $$$x_l \le x_s \le x_r$$$, the travelling time in $$$x$$$-coordinates is $$$d(s, z) + d(r, l) + \min(d(z, l), d(r, z))$$$. One can see that $$$d(s, z) + \min(d(z, l), d(r, z)) = \min(d(s, l), d(s, r))$$$, therefore any $$$z$$$ (including the endpoints, of course) is equally optimal. Proof for the above formula is trivial.
The optimal solution's time complexity is $$$\mathcal{O}(\log_2(t)^2)$$$.