1.3.4 Prime Cryptarithm 牛式

1.3.4 Prime Cryptarithm 牛式

时间: 1ms        内存:64M

描述:

下面是一个乘法竖式,如果用我们给定的那n个数字来取代*,可以使式子成立的话,我们就叫这个式子牛式。

      * * *
   x    * *
    -------
      * * *
    * * *
    -------
    * * * *

数字只能取代*,当然第一位不能为0,况且给定的数字里不包括0。

注意一下在美国的学校中教的“部分乘积”,第一部分乘积是第二个数的个位和第一个数的积,第二部分乘积是第二个数的十位和第一个数的乘积.

写一个程序找出所有的牛式。

输入:

Line 1:数字的个数n。 Line 2:N个用空格分开的数字(每个数字都∈ {1,2,3,4,5,6,7,8,9})。

输出:

 共一行,一个数字。表示牛式的总数。
 下面是样例的那个牛式。

        2 2 2
      x   2 2
    ---------
        4 4 4
      4 4 4
    ---------
     4 8 8 4

示例输入:

5
2 3 4 6 8

示例输出:

1

提示:

参考答案(内存最优[752]):

#include"stdio.h"
int a[10]={0},b[10];
int check(int x)
{
	while(x)
	{
		if(!a[x%10])return 0;
		x=x/10;
	}
	return 1;
}
int main()
{
	int n,i,j,k,p,q,sum1,sum,sum2,count;
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		scanf("%d",&b[i]);
		a[b[i]]=1;
	}
	count=0;
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			for(k=0;k<n;k++)
			{
				for(p=0;p<n;p++)
				{
					for(q=0;q<n;q++)
					{
						sum=b[i]*100+b[j]*10+b[k];
						sum1=sum*b[p];
						sum2=sum*b[q];
						if(sum1>999||sum2>999)continue;
						if(!check(sum1))continue;
						if(!check(sum2)&&sum2<=999)continue;
						sum=sum1+sum2*10;
						if(sum>9999)continue;
						if(!check(sum))continue;
						count++;
					}
				}
			}
		}
	}
	printf("%d\n",count);
}

参考答案(时间最优[3]):

#include"stdio.h"
int a[10]={0},b[10];
int check(int x)
{
	while(x)
	{
		if(!a[x%10])return 0;
		x=x/10;
	}
	return 1;
}
int main()
{
	int n,i,j,k,p,q,sum1,sum,sum2,count;
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		scanf("%d",&b[i]);
		a[b[i]]=1;
	}
	count=0;
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			for(k=0;k<n;k++)
			{
				for(p=0;p<n;p++)
				{
					for(q=0;q<n;q++)
					{
						sum=b[i]*100+b[j]*10+b[k];
						sum1=sum*b[p];
						sum2=sum*b[q];
						if(sum1>999||sum2>999)continue;
						if(!check(sum1))continue;
						if(!check(sum2)&&sum2<=999)continue;
						sum=sum1+sum2*10;
						if(sum>9999)continue;
						if(!check(sum))continue;
						count++;
					}
				}
			}
		}
	}
	printf("%d\n",count);
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注