Codeforces Round 614 (Div. 1) |
---|
Finished |
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:
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:
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?
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.
Print a single integer — the maximum number of data nodes Aroma can collect within $$$t$$$ seconds.
1 1 2 3 1 0 2 4 20
3
1 1 2 3 1 0 15 27 26
2
1 1 2 3 1 0 2 2 1
0
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:
In the second example, the optimal route to collect $$$2$$$ nodes is as follows:
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.
Name |
---|