比赛 东方幻想乡 S2 评测结果 AAAAAATATTATTTTTTTTT
题目名称 帕秋莉·诺蕾姬 最终得分 40
用户昵称 Truth.Cirno 运行时间 12.057 s
代码语言 C++ 内存使用 0.29 MiB
提交时间 2012-08-08 19:49:33
显示代码纯文本
#include <cstdio>
#include <cstring>
using namespace std;

struct bint
{
	int len,num[2001];
};

void swap(int& x,int& y)
{
	int temp;
	temp=x;
	x=y;
	y=temp;
}

bint bchange(int num)
{
	bint a={0};
	if (!num)
		return(a);
	while (num)
	{
		a.num[a.len++]=num%26;
		num/=26;
	}
	return(a);
}

bool bcom(bint a,bint b)
{
	int i;
	if (a.len>b.len)
	{
		return(0);
	}
	else if (a.len<b.len)
	{
		return(1);
	}
	else
	{
		for (i=a.len-1;i>=0;i--)
			if (a.num[i]>b.num[i])
			{
				return(0);
			}
			else if (a.num[i]<b.num[i])
			{
				return(1);
			}
	}
	return(0);
}

bint bmin(bint a,bint b)
{
	int i;
	bool jie=0;
	for (i=0;i<a.len;i++)
	{
		a.num[i]=a.num[i]-b.num[i]-jie;
		if (a.num[i]<0)
		{
			a.num[i]+=26;
			jie=1;
		}
		else
			jie=0;
	}
	for (i=a.len-1;i>=0;i--)
		if (a.num[i]!=0)
		{
			a.len=i+1;
			break;
		}
	if (i==-1)
		a.len=0;
	return(a);
}

bint bmod(bint a,bint b)
{
	if (a.len==0)
	{
		bint c={0};
		return(c);
	}
	if (bcom(a,b)==1)
		return(b);
	int i,len;
	len=a.len-b.len;
	for (i=b.len-1;i>=0;i--)
		b.num[i+len]=b.num[i];
	for (i=0;i<len;i++)
		b.num[i]=0;
	b.len=a.len;
	while (len!=-1)
	{
		while (bcom(a,b)==0)
			a=bmin(a,b);
		b.len--;
		len--;
		if (len!=-1)
			for (i=len;i<b.len;i++)
				b.num[i]=b.num[i+1];
		b.num[b.len]=0;
	}
	return(a);
}

int main(void)
{
	freopen("patchouli.in","r",stdin);
	freopen("patchouli.out","w",stdout);
	bint n={0},m={0},nt={0},temp={0};
	int i,j,M,type=0,a,b;
	char str[2005];
	scanf("%s%d",&str,&M);
	n.len=strlen(str);
	if (str[0]=='A'&&n.len==1)
		n.len=0;
	for (i=0,j=n.len-1;i<n.len;i++,j--)
		n.num[i]=str[j]-'A';
	m=bchange(M);
	temp=bmod(n,m);
	if (temp.len==0)
		type=1;
	if (!type)
	{
		for (i=n.len-1;!type&&i>=1;i--)
			for (j=i-1;!type&&j>=0;j--)
			{
				nt=n;
				swap(nt.num[i],nt.num[j]);
				temp=bmod(nt,m);
				if (temp.len==0)
				{
					type=2;
					a=n.len-i;
					b=n.len-j;
				}
			}
	}
	if (type==0)
		printf("-1 -1\n");
	else if (type==1)
		printf("0 0\n");
	else
		printf("%d %d\n",a,b);
	return(0);
}