首页 > 代码库 > USACO 1.3 Prime Cryptarithm （枚举）
USACO 1.3 Prime Cryptarithm （枚举）
描述
下面是一个乘法竖式，如果用我们给定的那n个数字来取代*，可以使式子成立的话，我们就叫这个式子牛式。
***
x **
----------
***
***
----------
****
数字只能取代*，当然第一位不能为0,况且给定的数字里不包括0。
注意一下在美国的学校中教的“部分乘积”，第一部分乘积是第二个数的个位和第一个数的积，第二部分乘积是第二个数的十位和第一个数的乘积.
写一个程序找出所有的牛式。
[编辑]格式
PROGRAM NAME: crypt1
INPUT FORMAT:
(file crypt1.in)
Line 1:数字的个数n。
Line 2:N个用空格分开的数字（每个数字都属于{1,2,3,4,5,6,7,8,9}）。
OUTPUT FORMAT:
(file crypt1.out)
共一行，一个数字。表示牛式的总数。
[编辑]SAMPLE INPUT
5 2 3 4 6 8
[编辑]SAMPLE OUTPUT
1
[编辑]样例分析
222
x 22
----------
444
444
----------
4884
注意：结果只能为4位
直接枚举，网上还有哈希搜索法，待会学习下
/*
ID:twd30651
PROG:crypt1
LANG:C++
*/
#include<iostream>
#include<fstream>
#include<stdlib.h>
#include<string.h>
using namespace std;
int n;
int a[10];
inline int check_num(int num,int len)
{
int num2=num;
while(num/10)//test num
{
if(a[num%10]==0)return 0;
num/=10;
}
if(a[num%10]==0)return 0;
int i=0;
while(num2/10)
{
num2/=10;
i++;
}
if(len!=i+1)return 0;
return 1;
}
int main(int argc,char *argv[])
{
freopen("crypt1.in","r",stdin);
freopen("crypt1.out","w",stdout);
memset(a,0,sizeof(a));
scanf("%d",&n);
int t;
for(int i=0;i<n;++i)
{
scanf("%d",&t);
a[t]=1;
}
int d,e;
int t1,t2,t3;
int count=0;
for(int i=100;i<=999;++i)
for(int j=10;j<=99;++j)
{
d=j/10;
e=j%10;
t1=d*i;
t2=e*i;
t3=t1*10+t2;
if(check_num(i,3)&&check_num(j,2)&&check_num(t1,3)&&check_num(t2,3)&&check_num(t3,4))
{
count++;
}
}
printf("%d\n",count);
return 0;
}
USACO 1.3 Prime Cryptarithm （枚举）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。