USaco 1.3 Prime Cryptarithm(単純ハッシュ表暴捜剪枝)
1332 ワード
考え方:
1.hash[]配列に入力した数字を格納し、hash[tmp]=1にします.
2.カスタム関数check()で、入力した数値を確認します.
3.暴捜.1行目は100から999、2行目は10から99です.
4.枝を切る.
コード:
1.hash[]配列に入力した数字を格納し、hash[tmp]=1にします.
2.カスタム関数check()で、入力した数値を確認します.
3.暴捜.1行目は100から999、2行目は10から99です.
4.枝を切る.
コード:
/*
ID: who jay
LANG: C++
TASK: crypt1
*/
#include<stdio.h>
bool hash[10]= {0};
bool check(int i)
{
while(i)
{
if(!hash[i%10])
return 1;
i/=10;
}
return 0;
}
int main()
{
freopen("crypt1.in","r",stdin);
freopen("crypt1.out","w",stdout);
int n,i,j,tmp,f1,f2,f3,s;
while(scanf("%d",&n)!=EOF)
{
for(i=0; i<n; i++)
{
scanf("%d",&tmp);
hash[tmp]=1;
}
s=0;
for(i=100; i<1000; i++)
{
if(check(i)) continue;
for(j=10; j<100; j++)
{
f3=i*j;
if(f3>9999) break;
if(check(j)) continue;
if(check(f3)||f3<1000) continue;
f1=i*(j%10);
if(f1>999||check(f1)||f1<100) continue;
f2=i*(j/10);
if(f2>999||check(f2)||f2<100) continue;
s++;
}
}
printf("%d
",s);
}
fclose(stdin);
fclose(stdout);
return 0;
}