2791033_wa.c

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>

int coin[51];
int h[230310];
int n, t, no;
int four[5], height;
int anss, ansb;

int gcd(int a,int b)
{
	int r;

	while(b)
	{
		r = a%b;
		a = b;
		b = r;
	}
	return a;
}

int lcm(int a,int b)
{
	return a*b/gcd(a,b);
}

void _enum(int st,int a)
{
	int i, tmp;

	if(a==0)
	{
		tmp = lcm(lcm(four[1],four[2]),lcm(four[3],four[4]));
		h[no++] = tmp;
		return ;
	}
	for(i = st; i <= n-a; i++)
	{
		four[a] = coin[i];
		_enum(i+1,a-1);
	}

}

int main()
{
	int i, j, tanss, tansb, tt, tmp;

	while(scanf("%d%d",&n,&t)==2)
	{
		if(n==0&&t==0)
			break;
		for(i = 0; i < n; i++)
			scanf("%d",&coin[i]);
		no = 0;
		_enum(0,4);
		for(i = 0; i < t; i++)
		{
			scanf("%d",&height);
			anss = 0;ansb = 2100000000;
			for(j = 0; j < no; j++)
			{
				if(height%tmp==0)
				{
					printf("%d %d\n",height,height);
					goto con;
				}
				else
				{
					tt = height/tmp;
					tanss = tmp*tt;
					tansb = tanss + tmp;
					if(tanss > anss&&tanss <= height)
						anss = tanss;
					if(tansb < ansb&&tansb >= height)
						ansb = tansb;
				}
			}
			printf("%d %d\n",anss,ansb);
con:
			;
		}
	}
	return 0;
}