暴力求出坐标在1e18范围里的点,然后依次枚举以i为起点,先收集小数据,再收集大数据的贪心策略
/* xi-x_i-1 = (ax-1)*x_i-1+bx yi-y_i-1 = (ay-1)*y_i-1+by ax,ay>=2,bx,by>=0 */ #include<bits/stdc++.h> using namespace std; #define ll long long #define N 200 ll x[N],y[N],ax,ay,bx,by; ll sx,sy,t; int n; int solve(int id){ ll res=0,sum=t; sum-=abs(sx-x[id])+abs(sy-y[id]); if(sum>=0)res++; else return 0; //从id往小走 int tmp=id; while(tmp){ sum-=(x[tmp]-x[tmp-1])+(y[tmp]-y[tmp-1]); if(sum<0)return res; res++; tmp--; } if(id==n)return res; //从0走到id+1 sum-=(x[id+1]-x[0])+(y[id+1]-y[0]); if(sum<0)return res; res++; tmp=id+1; while(tmp<n){ sum-=(x[tmp+1]-x[tmp])+(y[tmp+1]-y[tmp]); if(sum<0)return res; res++;tmp++; } return res; } int main(){ cin>>x[0]>>y[0]>>ax>>ay>>bx>>by; cin>>sx>>sy>>t;n=0; while(1){ double xx=1.0*ax*x[n]+bx; double yy=1.0*ay*y[n]+by; if(xx>1e18 || yy>1e18)break; x[++n]=ax*x[n-1]+bx; y[n]=ay*y[n-1]+by; } int ans=0; for(int i=0;i<=n;i++) ans=max(ans,solve(i)); cout<<ans<<'\n'; }