USACO Section1.3 Prime Cryptarithm 解题报告

　　　　crypt1解题报告 —— icedream61 博客园（转载请注明出处）
------------------------------------------------------------------------------------------------------------------------------------------------
【题目】
　　用给出的N个数字，替换以下竖式，能生成多少个正确的竖式？
　　* * *
　　x * *
　　-------
　　* * *
　　* * *
　　-------
　　* * * *
　　输入文件，第一行N表示有N个数字，第二行给出所有数字（空格分割。）
【数据范围】
　　所有数字∈{1,2,3,4,5,6,7,8,9}
【输入样例】
　　5
　　2 3 4 6 8
【输出样例】
　　1
------------------------------------------------------------------------------------------------------------------------------------------------
【分析】
　　竖式中，只要知道乘数和被乘数，就可以计算出下面三个结果。
　　因此，只要枚举这两个数就好，一共5位，9^5<100000，一定没问题。
------------------------------------------------------------------------------------------------------------------------------------------------
【总结】
　　一遍AC。
　　样例一开始本机测试没过，原因是乘出来的三个结果没判断位数是否正确。可以说，还是读题不够严谨仔细。

------------------------------------------------------------------------------------------------------------------------------------------------

【代码】

 /*

 ID: icedrea1

 PROB: crypt1

 LANG: C++

 */

 #include <iostream>

 #include <fstream>

 using namespace std;

 int N,D[];

 bool have[];

 bool ok(int num)

 {

     while(num)

     {

         if(!have[num%]) return false;

         num/=;

     }

     return true;

 }

 bool ok(int A,int B,int C,int D,int E)

 {

     int i = A*+B*+C;

     int j = D*+E;

     int x = i*E; if(x< || x>) return false;

     int y = i*D; if(y< || y>) return false;

     int z = x+y*; if(z< || z>) return false;

     return ok(x) && ok(y) && ok(z);

 }

 int main()

 {

     ifstream in("crypt1.in");

     ofstream out("crypt1.out");

     in>>N;

     for(int i=;i<=N;++i) { in>>D[i]; have[D[i]]=true; }

     int s=;

     for(int a=;a<=N;++a)

         for(int b=;b<=N;++b)

             for(int c=;c<=N;++c)

                 for(int d=;d<=N;++d)

                     for(int e=;e<=N;++e)

                         if(ok(D[a],D[b],D[c],D[d],D[e])) ++s;

     out<<s<<endl;

     in.close();

     out.close();

     return ;

 }