CodeForces 1293 D.Aroma's Search (思维、暴力)

D.Aroma’s Search

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 (x0,y0)
For i>0, the coordinates of i-th node is (ax⋅xi−1+bx,ay⋅yi−1+by)
Initially Aroma stands at the point (xs,ys). 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 (xs,ys) 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

The first line contains integers x0, y0, ax, ay, bx, by (1≤x0,y0≤10¹⁶, 2≤ax,ay≤100, 0≤bx,by≤10¹⁶), which define the coordinates of the data nodes.

The second line contains integers xs, ys, t (1≤xs,ys,t≤10¹⁶) – the initial Aroma’s coordinates and the amount of time available.

Output

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

Examples

Input

1 1 2 3 1 0
2 4 20

Output

3

Input

1 1 2 3 1 0
15 27 26

Output

2

Input

1 1 2 3 1 0
2 2 1

Output

0

题意：

给x[0],y[0],ax,ay,bx,by
其他每个点的坐标为:
x[i]=x[i-1]*ax+bx;
y[i]=y[i-1]*ay+by;
利用这个公式可以在二维平面衍生出无数的点

给起点xs,ys和时间t,每单位时间可以向四个方向任意走一步
问t步之内最多经过多少个不同的点

思路：

解题的关键点点在于题目的数据范围:
x0, y0, ax, ay, bx, by (1≤x0,y0≤10^16, 2≤ax,ay≤100, 0≤bx,by≤10^16)
xs, ys, t (1≤xs,ys,t≤10^16)

因为ax,ay>=2,bx,by>=0而公式:
x[i]=x[i-1]*ax+bx;
y[i]=y[i-1]*ay+by;

可以发现每个点的横纵坐标至少是上一个坐标的两倍(因为乘上了ax,bx,至少为2)
所以横纵坐标的增长至少是2的指数级别,而2^64已经超过题目的t范围1e16了
可以想到可以走的点的数量最多就60个左右,再后面是不可能走到的没有意义

所以利用公式先不断求点坐标,求出的坐标超过可达范围就停止

1.x和y都是一次函数增长且斜率为正,显然越后面的点越在右上方
2.一个点走到另一个点的花费的步数是曼哈顿距离
设d(i,j)表示点i到j的曼哈顿距离
由1,2可推出一个重要结论:
d(i,i+1)+d(i+1,i+2)=d(i,i+2)

由1可以想到点的位置近似是一条直线，
因此走的时候肯定照着顺序走过去而不是无序乱走
因为点最多60个,直接O(n^2)枚举要走的点的区间(枚举左右端点)
然后路径方向有两种:左端点->右端点,右端点->左端点
这两种路径花费的步数是一样的,但是题目要求从起点xs,ys开始走
所以所需时间time=min(起点到左端点,起点到右端点)+d(左端点,右端点)
如果时间time<=t则可行,更新ans为max(ans,区间长度)

code：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxm=105;
int x[maxm],y[maxm];
int ax,ay,bx,by;
int xs,ys,t;
int cnt;
int d(int a,int b,int x,int y){//曼哈顿距离
    return abs(a-x)+abs(b-y);
}
signed main(){
    cin>>x[0]>>y[0]>>ax>>ay>>bx>>by;//x[0]和y[0]也是一个点,所以下标从0开始
    cin>>xs>>ys>>t;
    while(x[cnt]-xs<t&&y[cnt]-ys<t){
        cnt++;
        x[cnt]=x[cnt-1]*ax+bx;
        y[cnt]=y[cnt-1]*ay+by;
    }
    int ans=0;
    for(int i=0;i<=cnt;i++){//枚举区间起点
        for(int j=i;j<=cnt;j++){//枚举区间终点
            if(j-i+1<=ans)continue;
            int temp=min(d(xs,ys,x[i],y[i]),d(xs,ys,x[j],y[j]));
            temp+=d(x[i],y[i],x[j],y[j]);
            if(temp<=t){
                ans=j-i+1;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}