前言

填一個月前的坑。這次比賽的題目品質很高，我到現在才改完。

題目

https://gmoj.net/senior/

題解

題目大意是給你一個網格圖，你可以以任意一點為中心進行任意次「十字變換」或「X型變換」。接著有T個詢問，每次問你能否通過變換把(x,y)弄到(0,0)。

比賽時考慮把X型變換全部變成十字變換，然而這其實並沒有用。

題目給的這個L是包括了變換中心的，可以把它去掉，令$l=L-1$。
發現對於一個座標$(x,y)$，可以進行如下操作（$1\le i\le l$）：

1. $(x\pm i,y\pm i)$
2. $(x\pm 2i,y)$
3. $(x,y\pm 2i)$

因為不同象限的點的走法是一樣的，為了方便處理，可以把每個點都翻折到第一象限中。
看到如上的走法，不難發現，若x和y的奇偶性不同，那麼無法到達。
還有一個重要的性質：斜著走最多隻會走兩次。
這裡給出證明（不妨把斜著走的那幾步都平移在起來，假設$(x,y)$連續斜著走了3次後變成$(x-step,y-step)$）

如果$step\le 2l$，那麼不如斜著走2步優；
如果$step>2l$，那麼前$2l$的路程可以通過操作2、3得到。

並且可以發現，如果斜著走了2步，當且僅當step是奇數。

然後下面就是貪心處理環節了（說真的，這題的貪心很難想到，要考慮的情況很多），不妨設x≥y，反之將x和y交換即可：

• 如果x+y是奇數，無解；
• 把(x,y)移動到較小的範圍，於是分別橫著走、豎著走，變成$(x\mathrm{m}\mathrm{o}\mathrm{d}2l,y\mathrm{m}\mathrm{o}\mathrm{d}2l)$（記為$(x^{\prime },y^{\prime })$），令$ans1=\lfloor \frac{x}{2l}\rfloor +\lfloor \frac{y}{2l}\rfloor$。
• 下面再進行分類討論：
  • 如果$y\ge 2l$，那麼可以讓x’或y’中的較小者最後一步少跳一點，使得兩者都變成較大值，從而用操作1解決問題，$ans2=\lfloor \frac{\max (x^{\prime },y^{\prime })}{l}\rfloor$；
  • 如果$x\ge 2l,且x^{\prime }\le y<2l$，那麼可以讓x’最後一步少跳一點，使得x’=y，再用操作1解決問題，$ans2=\lfloor \frac{y}{l}\rfloor$；
  • 考慮任意的$(x^{\prime },y^{\prime })$怎麼跳。不妨設x‘≥y’，反之將x‘和y’交換即可。如果$y^{\prime }\ge l$，那麼x‘和y’減去l，同時ans2加上1（下同）。接著再同時跳y‘步，此時座標為$(x^{\prime }-y^{\prime },0)$。如果此時x‘變成了奇數，就將它+1變回偶數（這只是第一次少跳一步而已，不是新的操作，目的是方便接下來的處理）。再用一次操作2解決問題。
  • 還有一種走法：$ans2=[x^{\prime }>0]+[y^{\prime }>0]+[2\nmid x^{\prime }]$。

這題最噁心的就是高精度運算了，好在可以不壓位。

CODE

#include<cstdio>
#include<cstring>
using namespace std;
#define P 100000000
#define N 505
int tmp[N];
inline char gc()
{
	static char buf[100005],*l=buf,*r=buf;
	return l==r&&(r=(l=buf)+fread(buf,1,100005,stdin),l==r)?EOF:*l++;
}
struct bignum
{
	long long a[N];int len;
	bignum(){memset(a,0,sizeof a),len=1;}
	inline void clear(){memset(a,0,sizeof a),len=1;}
	inline void read()
	{
		char ch;int cnt=1;
		memset(a,0,sizeof a);
		while(ch=gc(),ch<'0'||ch>'9');tmp[1]=ch-'0';
		while(ch=gc(),ch>='0'&&ch<='9') tmp[++cnt]=ch-'0';
		len=cnt>>3;if(len<<3<cnt) ++len;
		for(int i=cnt,k=1;k<=len;i-=8,++k)
			for(int j=7;j>=0;--j) if(i>j) a[k]=a[k]*10+tmp[i-j];
	}
	inline void print()
	{
		printf("%lld",a[len]);
		for(int i=len-1;i;--i) printf("%08lld",a[i]);
		putchar('\n');
	}
}_1,_0,re,inf;//re是餘數
inline int mymax(int x,int y){return x>y?x:y;}
inline bignum move(bignum x)
{
	if(x.len==1&&!x.a[1]) return x;
	for(int i=x.len;i;--i) x.a[i+1]=x.a[i];
	++x.len,x.a[1]=0;
	return x;
}
inline bool judge(bignum x,bignum y) // x>y
{
	if(x.len^y.len) return x.len>y.len;
	for(int i=x.len;i;--i)
		if(x.a[i]^y.a[i]) return x.a[i]>y.a[i];
	return 0;
}
inline bignum plus(bignum x,bignum y)
{
	bignum z;
	z.len=mymax(x.len,y.len);
	for(int i=1;i<=z.len;++i)
	{
		z.a[i]=x.a[i]+y.a[i];
		if(z.a[i]>=P) z.a[i]-=P,++x.a[i+1];
	}
	if(z.a[z.len+1]) ++z.len;
	return z;
}
inline bignum plus(bignum x,int y)
{
	x.a[1]+=y;
	for(int i=1;i<=x.len&&x.a[i]>=P;++i)
		++x.a[i+1],x.a[i]-=P;
	if(x.a[x.len+1]) ++x.len;
	return x;
}
inline bignum minus(bignum x,bignum y)
{
	for(int i=1;i<=x.len;++i)
	{
		x.a[i]-=y.a[i];
		if(x.a[i]<0) x.a[i]+=P,--x.a[i+1];
	}
	while(x.len>1&&!x.a[x.len]) --x.len;
	return x;
}
inline bignum times(bignum x,int y)
{
	if(!y) return _0;
	bignum z;z.len=x.len;
	for(int i=1;i<=x.len;++i)
	{
		z.a[i]+=x.a[i]*y;
		z.a[i+1]+=z.a[i]/P;
		z.a[i]%=P;
	}
	while(z.a[z.len+1])
	{
		++z.len;
		z.a[z.len+1]+=z.a[z.len]/P;
		z.a[z.len]%=P;
	}
	return z;
}
inline bignum div(bignum x,bignum y) // ceil(x/y)
{
	bignum z;
	z.len=x.len,re.clear();
	for(int i=z.len,l,r,mid,num;i;--i)
	{
		re=plus(move(re),x.a[i]);
		l=num=0,r=P-1;
		while(l<=r)
		{
			mid=l+r>>1;
			if(judge(times(y,mid),re)) r=mid-1;
			else l=mid+1,num=mid;
		}
		re=minus(re,times(y,num));
		z.a[i]=num;
	}
	while(z.len>1&&!z.a[z.len]) --z.len;
	return z;
}
inline bignum max(bignum x,bignum y){return judge(x,y)?x:y;}
inline bignum min(bignum x,bignum y){return judge(y,x)?x:y;}
inline int calc(bignum x,bignum y,bignum l) // (x,y)->(0,0) y<=x<2l
{
	int s=0;
	if(!judge(l,y)) x=minus(x,l),y=minus(y,l),++s;
	if(!judge(x,_0)) return s;
	if(x.a[1]&1) x=plus(x,1),y=plus(y,1);
	x=minus(x,y),++s;
	return s+judge(x,_0);
}
int main()
{
	bignum ans1,ans2,x,y,l,_2l,xx,yy,z;
	int t;_1.a[1]=1;
	scanf("%d",&t);
	inf.len=500;for(int i=1;i<501;++i) inf.a[i]=P-1;
	while(t--)
	{
		x.read(),y.read(),l.read();
		if(judge(y,x)) z=x,x=y,y=z;
		if(x.a[1]+y.a[1]&1) puts("Poor MLG!");
		else
		{
			l=minus(l,_1);
			_2l=times(l,2);
			ans1=div(x,_2l),xx=re;
			ans1=plus(ans1,div(y,_2l)),yy=re;
			if(judge(yy,xx)) z=xx,xx=yy,yy=z;
			if(!judge(_2l,y)) ans2=div(xx,l),ans2=plus(ans2,judge(re,_0));
			else if((!judge(_2l,x))&&!judge(xx,y)) ans2=div(y,l),ans2=plus(ans2,judge(re,_0));
			else ans2=inf;
			ans2=min(min(ans2,plus(_0,calc(xx,yy,l))),plus(_0,judge(xx,_0)+(int)judge(yy,_0)+((xx.a[1]&1)?1:0)));
			ans1=plus(ans1,ans2),ans1.print();
		}
	}
	return 0;
}