coreBugZJ

此 blog 已弃。

A hard Aoshu Problem, ACM/ICPC 2010/2011 亚洲,福州区域赛 J, UVA 5107

5107 - A hard Aoshu Problem
Asia - Fuzhou - 2010/2011

 

Math Olympiad is called ``Aoshu" in China. Aoshu is very popular in elementary schools. Nowadays, Aoshu is getting more and more difficult. Here is a classic Aoshu problem:

 

 

ABBDE$\displaystyle \_$$\displaystyle \_$$\displaystyle \_abccc$ = BDBDE

In the equation above, a letter stands for a digit(0 - 9), and different letters stands for different digits. You can fill the blank with `+', `-`, ` x' or `÷'.

How to make the equation right? Here is a solution:

 

 

12245 + 12000 = 24245

In that solution, A = 1, B = 2, C = 0, D = 4, E = 5, and `+' is filled in the blank.

When I was a kid, finding a solution is OK. But now, my daughter's teacher tells her to find all solutions. That's terrible. I doubt whether her teacher really knows how many solutions are there. So please write a program for me to solve this kind of problems.

 

Input 

The first line of the input is an integer T (T$ \le$20) indicating the number of test cases.

Each test case is a line which is in the format below:

 


s1 s2 s3

 


s1, s2 and s3 are all strings which are made up of capital letters. Those capital letters only include ` A',' B', ' C',' D' and ` E', so forget about ` F' to ` Z'. The length of s1, s2 or s3 is no more than 8.

When you put a `=' between s2 and s3, and put a operator (`+','-`, ` x' or `÷'.) between s1 and s2, and replace every capital letter with a digit, you get a equation.

You should figure out the number of solutions making the equation right.

Please note that same letters must be replaced by same digits, and different letters must be replaced by different digits.

If a number in the equation is more than one digit, it must not have leading zero.

 

Output 

For each test case, print an integer in a line. It represents the number of solutions.

 

Sample Input 

 

2 
A A A
BCD BCD B

 

Sample Output 

 

5
72

Fuzhou 2010-2011


暴力搜索之。。。

我的代码:

 1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 typedef long long Lint;
 5 
 6 #define  L  10
 7 
 8 char s1[ L ], s2[ L ], s3[ L ];
 9 
10 #define  DIGIT  6
11 
12 int digit[ DIGIT ], used[ DIGIT ];
13 int a[ L ], b[ L ], c[ L + L ];
14 
15 void parse( char s[], int a[], int size ) {
16         int i, len = strlen( s );
17         memset( a, 0, size );
18         for ( i = 0; i < len; ++i ) {
19                 used[ a[ len - i - 1 ] = s[ i ] - 'A' + 1 ] = 1;
20         }
21 }
22 
23 void init() {
24         memset( used,  0sizeof(used)  );
25         parse( s1, a, sizeof(a) );
26         parse( s2, b, sizeof(b) );
27         parse( s3, c, sizeof(c) );
28 }
29 
30 int parseInt( int a[], int n, Lint *num ) {
31         int i = n-1;
32         while ( (i>=0&& (a[i]==0) ) --i;
33         if ( (i<0|| ((i>0)&&(digit[a[i]]==0)) ) return 0;
34         *num = 0;
35         for ( ; i >= 0--i ) {
36                 if ( digit[ a[ i ] ] > 9 ) return 0;
37                 *num = (*num) * 10 + digit[ a[ i ] ];
38         }
39         return 1;
40 }
41 
42 int equal() {
43         Lint x, y, z;
44         int i, ans = 0;
45         for ( i = 1; i < DIGIT; ++i ) {
46                 if ( (digit[i]<10&& (used[i]==0) ) {
47                         return 0;
48                 }
49         }
50         if ( !parseInt( a, sizeof(a)/sizeof(a[0]), &x ) ) return 0;
51         if ( !parseInt( b, sizeof(b)/sizeof(b[0]), &y ) ) return 0;
52         if ( !parseInt( c, sizeof(c)/sizeof(c[0]), &z ) ) return 0;
53         if ( x + y == z ) ++ans;
54         if ( x - y == z ) ++ans;
55         if ( x * y == z ) ++ans;
56         if ( (y!=0&& (x%y==0&& (x/y==z) ) ++ans;
57         return ans;
58 }
59 
60 int solve() {
61         int ans = 0, have[ 22 ] = { 0 };
62 #define  F(i) for ( digit[ i ] = 0; digit[ i ] < 11; ++digit[ i ] ) { \
63                 if ( have[ digit[ i ] ] ) continue; \
64                 if ( digit[ i ] < 10 ) have[ digit[ i ] ] = 1;
65 #define  E(i)  have[ digit[ i ] ] = 0; \
66         }
67         F(1) F(2) F(3) F(4) F(5) {
68                 ans += equal();
69         } E(5) E(4) E(3) E(2) E(1)
70         return ans;
71 }
72 
73 int main() {
74         int td;
75         scanf( "%d"&td );
76         while ( td-- > 0 ) {
77                 scanf( "%s%s%s", s1, s2, s3 );
78                 init();
79                 printf( "%d\n", solve() );
80         }
81         return 0;
82 }
83 


posted on 2011-03-24 22:14 coreBugZJ 阅读(1974) 评论(3)  编辑 收藏 引用 所属分类: ACM

Feedback

# re: A hard Aoshu Problem, ACM/ICPC 2010/2011 亚洲,福州区域赛, UVA 5107 2011-03-25 09:53 电脑知识与技术

全都是英文。看不懂啊  回复  更多评论   

# re: A hard Aoshu Problem, ACM/ICPC 2010/2011 亚洲,福州区域赛, UVA 5107[未登录] 2011-03-25 15:45 Bill

纯建议,不要一次发一堆文章到主页上。可以慢慢发。  回复  更多评论   

# re: A hard Aoshu Problem, ACM/ICPC 2010/2011 亚洲,福州区域赛, UVA 5107 2011-03-25 16:21 coreBugZJ

@Bill
我是刚来的菜鸟,不懂事,谢谢提醒。。。  回复  更多评论   



只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理