ariprog.cpp

USACO Section 1-4的后两个程序以及Section 1-5的全部程序代码

/*
NAME:lemon_c1
PROG:ariprog
LANG:C++
*/
#include<iostream>
using namespace std;
int n,m;
bool able[125001];
int array[25001];
class node
{
	public:
		int st,d;
		operator int ()
		{
			return d;
		}
		friend ostream & operator << (ostream &o,node &s)
		{
			o<<s.st<<' '<<s.d;
			return o;
		}
}output[10001];
int s_array;
inline bool verify(int a1,int d)
{
	if(a1+d*(n-1)>2*m*m)return false;
	for(int i=2;i<n;i++)
		if(!able[a1+i*d])return false;
	return true;
}
int cmp(const void *t1,const void *t2)
{
	if((*(node *)t1)>(*(node *)t2))return 1;
	if((*(node *)t2)>(*(node *)t1))return -1;
	return ((*(node *)t1).st-(*(node *)t2).st);
}
int main(void)
{
	freopen("ariprog.in","r",stdin);
	freopen("ariprog.out","w",stdout);
	cin>>n>>m;
	for(int i=0;i<=m;i++)
		for(int j=i;j<=m;j++)
			able[i*i+j*j]=true;
	for(int i=0;i<=125000;i++)
		if(able[i])array[s_array++]=i;
	int cnt=0;
	for(int st_i=0;st_i<s_array;st_i++)
	{
		int st=array[st_i];
		for(int i=st_i+1;i<s_array;i++)
		{
			int d=array[i]-st;
			if(verify(st,d))
			{
				output[cnt].st=st;
				output[cnt++].d=d;
			}
		}
	}
	if(cnt==0)cout<<"NONE"<<endl;
	else
	{
		qsort(output,cnt,sizeof(node),cmp);
		for(int i=0;i<cnt;i++)
			cout<<output[i]<<endl;
	}
	return 0;
}