1252.cpp

来自「这些是我到目前在PKU上做出的题目」· C++ 代码 · 共 67 行

#include <stdio.h>

int need[201],his[2][201],n,i,j,coin[7],max,t,ii,l,f;

int main()
{
	scanf("%d",&n);
	for (ii=1;ii<=n;ii++)
	{
		for (i=1;i<=6;i++)
			scanf("%d",&coin[i]);
		max=1;t=6;l=0;
		for (i=1;i<=200;i++)
			need[i]=0;
		his[0][0]=6;f=6;
		for (i=1;i<=6;i++)
		{
			his[0][i]=coin[i];
			need[coin[i]]=1;
		}
		while (f<200)
		{
			max++;
			his[(l+1)%2][0]=0;
			for (i=1;i<=his[l][0];i++)
			{
				for (j=1;j<=6;j++)
				{
					if (his[l][i]-coin[j]>=1)
						if (need[his[l][i]-coin[j]]==0)
						{
							need[his[l][i]-coin[j]]=max;
							if (his[l][i]-coin[j]<=100) 
								t=t+max;
							his[(l+1)%2][0]++;
							his[(l+1)%2][his[(l+1)%2][0]]=his[l][i]-coin[j];
							f++;
						}
					if (his[l][i]+coin[j]<=200)
						if (need[his[l][i]+coin[j]]==0)
						{
							need[his[l][i]+coin[j]]=max;
							if (his[l][i]+coin[j]<=100)
								t=t+max;
							his[(l+1)%2][0]++;
							his[(l+1)%2][his[(l+1)%2][0]]=his[l][i]+coin[j];
							f++;
						}
				}
			}
			l=(l+1)%2;
		}
		max=0;
		for (i=1;i<=100;i++)
			if (max<need[i])
				max=need[i];
		printf("%.2f %d\n",t/100.0,max);
	}
	return 0;
}