首先根据数据范围可以知道,数据点最多只有50多个,因此这道题可以暴力来解
另外我们还知道,最优解的数据点一定是连续的,因为第\(i+1\)个点必然在第\(i\)个点的右上方。
因为其数据范围很小,所以我们只需要遍历所有的情况即可。
代码:
// Created by CAD on 2020/1/19.
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll ax,ay,bx,by,xs,ys,X,Y,t;
ll x[60],y[60];
const ll inf=1e17;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> x[0] >> y[0] >> ax >> ay >> bx >> by;
cin>>xs>>ys>>t;
int n=0;
while((inf-bx)/ax>=x[n]&&(inf-by)/ay>=y[n])
n++,x[n]=(ax * x[n-1] + bx),y[n]=(ay * y[n-1] + by);
int ans=0;
for(int i=1;i<=n+1;++i)
for(int l=0;l+i-1<=n;++l)
{
int r=l+i-1;
ll len=x[r]-x[l]+y[r]-y[l];
ll dl=abs(xs-x[l])+abs(ys-y[l]);
ll dr=abs(xs-x[r])+abs(ys-y[r]);
if(dl<=t-len||dr<=t-len) ans=max(ans,i);
}
cout<<ans<<endl;
return 0;
}